题目描述
小明有一个容量为 V 的背包。
这天他去商场购物，商场一共有 N 件物品，第 i 件物品的体积为 wi,价值为 vi。
小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少。
解题思路
现假设 V 为 7，N 为 4，他们的 w 分别为 1，3，4，5 。v 分别为1，4，5，7。
要想解决这个问题可以先建立一个 N 行 V 列的二位数组，即解决此问题的dp数组，值为此时背包可装下物品的最大价值。
解题过程
当背包容积为0时，无法装下任意体积的商品，故第一列全为零，即最大价值为0。
现在我们逐行进行遍历：
（1）当背包容积为1时，我们发现刚好可以装下第一个物品（体积为1），此时背包可装物品的最大价值为1，第一行都是这种情况。
（2）第二行，当背包容量为1，2时，不能选择装入第一个物品（因为w2=3大于此时背包容量），故此时能装入的最大价值和上一行一样，即dp[i][j]=dp[i-1][j]。
（3）当体积为3时，此时是可以装下第二个物品的，但是要分两种情况讨论：1.装第二个物品；2.不装第二个物品。
情况1：装下第二个物品后，背包剩余体积为 j-w[2]=0，此时不能再装下其他物品了，故该情况的最大价值为4。
情况2：不装第二个物品，此时的最大价值和上一行一样，即dp[i][j]=dp[i-1][j]，即为1.
总结：通过比较两种情况发现，情况1的价值（val=4）比情况2的价值（val=1）大，所以这里选择装第二件物品，转化为dp公式就是：dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+val[i])。
（到这里可能就有小伙伴不理解 dp[i][j-w[i]]+val[i] 了，别急！听我细细道来！）
显而易见，dp[i][j-w[i]]+val[i]中的 +val[i] 部分就是刚刚的情况2，那为什么要有前面的 dp[i][j-w[i]] 呢？
刚刚情况2直接得出最大价值val[2]是4，没有 dp[i][j-w[i]] 是因为装下第二件物品后背包的剩余容易为零了。我们再看刚刚的dp[i][j-w[i]] 不就是dp[2][0]=0吗？所以刚刚情况2的完整写法应该是最大价值是0+4=4。
关键代码
for (int i = 1; i <= n; i++) {
for (int j = 1; j <=v; j++) {
if(wei[i]>j) {
dp[i][j]=dp[i-1][j];
}else {
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-wei[i]]+val[i]);
}
}
}
完整代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int v=sc.nextInt();
int[][] dp=new int[n+1][v+1];
int[] val=new int[n+1];
int[] wei=new int[n+1];
for (int i = 1; i < n+1; i++) {
wei[i]=sc.nextInt();
val[i]=sc.nextInt();
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <=v; j++) {
if(wei[i]>j) {
dp[i][j]=dp[i-1][j];
}else {
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-wei[i]]+val[i]);
}
}
}
System.out.println(dp[n][v]);
}
}