有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。

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];
    }
}

===============Talk is cheap, show me the code=================