有n个重量和价值分别为wi,vi的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。
限制条件：
1≤n≤100
1≤wi,vi≤100
1≤W≤10000
例如输入：
n = 4
W=5
2 3 (分别为w，v)
1 2
3 4
2 2
输出
7
如果是普通的递归，搜索的深度就是n，并且每一层的搜索都需要2次分支，n比较大的时候就没办法解
第二种就是动态规划表(也可以用递归版的动态规划)，这里
weight[4]={2,1,3,2}
value[4] = {3,2,4,2}
dp[i][j]表（最大价值表），代表获得最大价值的递推关系表
i j | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
0 | 7 | 6 | 5 | 3 | 2 | 0 |
1 | 6 | 6 | 4 | 2 | 2 | 0 |
2 | 6 | 4 | 4 | 2 | 0 | 0 |
3 | 2 | 2 | 2 | 2 | 0 | 0 |
4 | 0 | 0 | 0 | 0 | 0 | 0 |
从右下往左上，j是背包已经装的重量，加上weight[i]重量的物品能够获得的最大价值，最底下一行作为辅助空间。
思路是：已经装了重量j时，是否还可以装入第i件物品weight[i]的重量。
dp[i][j]意思是从后往前在计算第i件物品时能装入的最大价值，dp[0][0]就是从后往前遍历完之后到第0件物品能装入的最大价值。也就是我们需要求的最大价值。
weight[0]表示第零件物品的重量。
从i=3开始，如果已经装的重量为5，什么都装不了，价值为0。
i=3时:
若j=4，背包已经装了4重量时，是否可以装下第三件物品重量weight[3]=2呢？j weight[3]=4 2=6>5，所以不可以。这里最大价值dp[3][4]=0。
若j=3，背包已经装了3重量时，是否可以装下第三件物品重量weight[3]=2呢？j weight[3]=3 2=5可以！获得了价值value[3]=2。所以最大价值dp[3][3]=2。
若j=2..j=1...j=0也是一样，第三件物品的重量weight[3]=2都可以放下，也就是背包已经装了3重量，2重量，1重量，0重量时，在这个步骤再装还能获得的最大价值为2。所以同样的最大价值dp[3][2]=dp[3][1]=dp[3][0]=2。
i=2时:
若j=5，背包已达最大重量，什么都装不了，最大价值为0！
若j=4，背包已经装了4重量时，是否可以装下第2件物品重量weight[2]=3？j weight[2]=4 3=7 > W=5，装不了第2件物品，那么只好听从上一步结果，最大价值为dp[2][4]=dp[3][4]=0。
若j=3，背包已经装了3重量时，是否可以装下第2件物品重量weight[2]=3？j weight[2]=3 3=6 > W=5，装不了第2件物品，那么只好听从上一步结果，最大价值为dp[2][3]=dp[3][3]=2。
若j=2，背包已经装了2重量时，是否可以装下第2件物品重量weight[2]=3？j weight[2]=2 3<=5成立，能装第2件物品！那么在上一步装的基础上再装weight[2]，重量就是2 weight[2]。最大价值为dp[2][2]=value[2] dp[3][2 weight[2]=5]=4 0=4;即最大价值dp[2][2]=max(dp[2][2], 4 dp[3][5])=4。而dp[2][2]我们可以先将dp[3][2]的值赋给它，这样就是可以比较装weight[2]时（此时价值value[2] dp[3][2 weight[2]]）和不装weight[2]时(此时价值dp[3][2])最大价值的区别。那dp[3][2 weight[2]]又是什么意思？刚刚我们从表的底部往上的时候计算了第3行的呀，就是在上一步计算出的在对应位置能获得的最大价值，既然上一步算过了，这一步还操什么心？现在就只看i=2时的第二行！！！
若j=1，背包已经装了1重量时，是否可以装下第2件物品重量weight[2]=3？或者第三件物品重量weight[3]=2？但是无法同时装下2样。
如果装weight[3]=2，那么价值value[3]为2，dp[2][1]=max(dp[2][1], value[3] dp[3][1 weight[3]=3])。即dp[2][1]=max(dp[2][1],
2 dp[3][3])=4。
如果装备weight[2]=3，value[2]=4，那么价值为dp[2][1]=max(dp[2][1], value[2] dp[3][1 weight[2]=4])。即dp[2][1]=max(dp[2][1], 4 dp[3][4])=4。两种情况的最大价值均为4，其实不同只有剩余背包的可装重量不同，前者还剩2，后者还剩1。
若j=0，背包已经装了0重量时，是否可以装下第2件物品重量weight[2]=3？可以装上第二件weight[2]=3和第三件weight[3]=2，装上之后总重量正好为5，所以此时的总价值是value[2] value[3]=4 2=6，那么价值dp[2][0]=max(dp[2][0],
value[2] dp[3][0 weight[2]=3])=max(dp[2][0], 4 dp[3][3])=6。
而dp[3][3]在我们从下往上计算的时候已经算过了，不管是什么意思，反正刚刚一定正确计算了(因为上一步单独算过只装第三件weight[3]了，此时只算装上第二件weight[2]就行了)，直接用。
dp[2][0]=max(dp[2][0], 4 2)=6。
显然两件同时装比只装其中一件获得的总价值更高。
......同理推到左上，动笔记录打草稿，这样才看的懂意思，这个确实很难理解
最后dp[0][0]=max(dp[0][0], value[0] dp[1][0 weight[0]=2])，即dp[0][0]=max(dp[0][0], 3 4)=7。
代码语言：javascript复制import java.io.BufferedInputStream;
import java.util.Scanner;
public class test {
public static int[] weight = new int[101];
public static int[] value = new int[101];
public static void main(String[] args) {
Scanner cin = new Scanner(new BufferedInputStream(System.in));
int n = cin.nextInt();
int W = cin.nextInt();
for (int i = 0; i < n; i) {
weight[i] = cin.nextInt();
value[i] = cin.nextInt();
}
cin.close();
System.out.println(solve(0, W, n)); // 普通递归
System.out.println("=========");
System.out.println(solve2(weight, value, W)); // 动态规划表
}
public static int solve(int i, int W, int n) {
int res;
if (i == n) {
res = 0;
} else if (W < weight[i]) {
res = solve(i 1, W, n);
} else {
res = Math.max(solve(i 1, W, n), solve(i 1, W - weight[i], n) value[i]);
}
return res;
}
public static int solve2(int[] weight, int[] value, int W) {
int[][] dp = new int[weight.length 1][W 1];
for (int i = weight.length - 1; i >= 0; --i) {
for (int j = W; j >= 0; --j) {
dp[i][j] = dp[i 1][j]; // 从右下往左上，i 1就是刚刚记忆过的背包装到i 1重量时的最大价值
if (j weight[i] <= W) { // dp[i][j]就是背包已经装了j的重量时，能够获得的最大价值
dp[i][j] = Math.max(dp[i][j], value[i] dp[i 1][j weight[i]]);
// 当背包重量为j时，要么沿用刚刚装的，本次不装，最大价值dp[i][j]，要么就把这个重物装了，那么此时背包装的重量为j weight[i]，
// 用本次的价值value[i]加上背包已经装了j weight[i]时还能获得的最大价值，因为是从底下往上，刚刚上一步算过，可以直接用dp[i 1][j weight[i]]。
// 然后选取本次不装weight[i]重物时获得的最大价值以及本次装weight[i]重物获得的最大价值两者之间的最大值
}
}
}
return dp[0][0];
}
}
