一、题目描述
给定n(n<=100)种物品和一个背包。物品i的重量是wi(wi<=100)，价值为vi(vi<=100)，背包的容量为C(C<=1000)。
应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品i装入多次，也不能只装入部分物品i。
输入格式:
共有n+1行输入：
第一行为n值和c值，表示n件物品和背包容量c；
接下来的n行，每行有两个数据，分别表示第i(1≤i≤n)件物品的重量和价值。
输出格式:
输出装入背包中物品的最大总价值。
输入样例:
在这里给出一组输入。例如：
5 10
2 6
2 3
6 5
5 4
4 6
输出样例:
在这里给出相应的输出。例如：
15二、解题思路
1、dp数组所代表的含义：dp[i] [j]代表从下标[0-i]的物品里任意取，放进容量为j的背包，最大价值为多少。
2、dp数组的递推公式：dp[i] [j] =max(dp[i-1] [j]，dp[i-1] [j-weight[i]]+value[i]);
对于第i个物品，只有放入背包或者不放入背包两种情况，所以比较这两种情况的价值，取最大值。
①若第i个物品不放入背包：当前背包容量不改变。那么由dp数组的含义，说明从[0 - i-1]的物品任意取，放入容量为j的背包。即dp[i-1] [j];
②若第i个物品放入背包：那我们需要先将当前的背包容量j空出第i个物品的重量weight[i] （ 因为我们选择了把第i个物品装入背包，那么背包一定先要有第i个物品，所以容量减去weight[i]）。再在此基础上来考虑任取[0 - i-1]物品装入剩余的背包容量中能取得的最大价值，由dp数组的含义可得dp[i-1] [j-weight[i]]，而这种情况在我们考虑是否把第i-1个物品放入背包时已经被计算过并保存在了dp数组里了（如同现在考虑的第i个物品一样）。 于是，把第i个物品放入背包时的最大价值为：任取前i-1个物品放入背包容量为j-weight[i]的最大价值dp[i-1] [j-weight[i]]+第i个物品的价值value[i]，即dp[i] [j-weight[i]]+value[i]；
3、dp数组的初始化
dp数组的初始化需与dp数组的含义相吻合。
①当背包容量为0时，任何物品都无法装入背包，所以最大价值dp[i] [0]=0；
②由dp数组的递推公式：dp[i] [j] =max(dp[i-1] [j]，dp[i-1] [j-weight[i]]+value[i]);可知，i是由i-1推导而来，所以i-1必须初始化。
当背包容量j小于物品0的重量weight[0]时，物品i无法放入背包，则dp[0] [j]=0；当j>=weight[0]时，物品i能放入背包，则dp[0] [j]=value[i]；
假设物品0的weight[0]=2，value[0]=15。则此时的dp[i] [j]如下图：
③至于其他区域的dp[i] [j]的初始化其实无所谓，因为它们的数值都是由前面的数值推导而来，会被推导得到的数值覆盖。所以我们一般会初始化为0。
4、遍历顺序
dp数组为二维数组，所以给它赋值需有两重循环。先遍历物品还是先遍历背包容量都可以。因为由dp数组的递推公式：dp[i] [j] =max(dp[i-1] [j]，dp[i-1] [j-weight[i]]+value[i])可知，所求dp[i] [j]的值由dp[i] [j]的左上角的值推导而来，无论先遍历物品还是先遍历背包容量，在求dp[i] [j]的值时，dp[i] [j]的左上角区域都已经正确赋值，可以动手推导试试。
5、举例推导dp数组
例：背包的最大容量为4。
物品为：
求背包能背的物品的最大价值。
三、代码
import java.util.Scanner;
public class KnapsackProblem {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//读取物品数量n和背包容量c
int n=sc.nextInt();
int c=sc.nextInt();
//初始化物品重量和价值数组
int weight[]=new int[n];
int value[]=new int[n];
// 读取每个物品的重量和价值
for (int i = 0; i < n; i++) {
weight[i] = sc.nextInt();
value[i] = sc.nextInt();
}
//创建dp数组，大小为 n * (c+1)，初始化为0
int dp[][]=new int[n][c+1];
//初始化只放入物品0的情况
for (int j = weight[0]; j <= c; j++) {
dp[0][j] = value[0];
}
// 填充dp数组
for (int i = 1; i < n; i++) {
for (int j = 0; j <= c; j++) {
if (j < weight[i]) {//此时物品重量比背包容量大，无法装入物品i
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
}
// 输出结果
System.out.println(dp[n-1][c]);
}
}
