01背包问题(动态规划)

有n个重量和价值分别为w_i,v_i的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。

限制条件：

1≤n≤100

1≤w_i,v_i≤100

1≤W≤10000

例如输入：

n = 4

W=5

2 3 (分别为w，v)

1 2

3 4

2 2

输出

如果是普通的递归，搜索的深度就是n，并且每一层的搜索都需要2次分支，n比较大的时候就没办法解

第二种就是动态规划表(也可以用递归版的动态规划)，这里

weight[4]={2,1,3,2}

value[4] = {3,2,4,2}

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]重量的物品能够获得的最大价值

若i=3，j=4，背包已经装了4重量，装不下weight[3]=2，若j=3，背包已经装了3重量，那么可以装下weight[3]=2重量，value[3]=2,所以最大价值为2，j=2..j=1...j=0也是一样，只有weight[3]=2的物品可以装，也就是背包已经装了3重量，2重量，1重量，0重量时，在这个步骤再装还能获得的最大价值为2

若i=2, j=5,装不了，不予考虑。

j=4,装不了weight[2]=3，j+weight[2]=7 > W=5

若j=3，也装不了，j+weight[2]=6 > W=5

j=2时，可以装下weight[2]=3，如果装，那么最大价值就是value[2]=4,如果不装，沿用刚刚下面算过的dp[i+1][j]=2，显然这里最大价值是4。

j=1，可以装weight[2]或者weight[3]，但是无法同时装下2样，所以同上，最大价值为4。

若j=0，如果不装weight[2]，沿用下面刚刚算的装了weight[3]=2的物品，最大价值为2，如果要装，那么装上weight[2]=3，value[2]=4,此时背包已经装了3重量，也就是装了j+weight[i]=0+3=3时，再装物品还能获得的最大价值，上一步算过，装了重量为3时再装其他物品的最大价值就是2，此时value[2]=4加上2就是6价值，最大价值为6

......同理推到左上，请务必动笔记录打草稿，这样才看的懂意思，这个确实很难理解

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

=============================我是一个反应迟钝的程序员==========================

秒客网

01背包问题(动态规划)

相关文章