题目描述

已知一个背包最多能容纳物体的体积为V
现有n个物品第i个物品的体积为v_i，第i个物品的重量为w_iw
求当前背包最多能装多大重量的物品

示例1

输入
10,2,[[1,3],[10,4]]
返回值
4
说明
第一个物品的体积为1，重量为3，第二个物品的体积为10，重量为4。只取第二个物品可以达到最优方案，取物重量为4

思路

1. 递推如下：
2. 包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)
3. 还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝。

code

import java.util.*;
public class Solution {
    public int knapsack (int V, int n, int[][] vw) {
        int dp[][] = new int[n+1][V+1];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=V;j++){
                int v=vw[i-1][0],w=vw[i-1][1];
                if(j<v)
                    dp[i][j]=dp[i-1][j];
                else
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-v]+w);
            }
        return dp[n][V];
    }
}