二维数组完全背包与01背包 状态转移方程的不同点_完全背包二维

二维数组完全背包的状态转移方程与01背包的不同点：

0-1背包问题：

dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])；

• dp[i-1][j]: 是指 不选择第i件物品， 将前 i - 1 的物品放入 容量为j的价值。
• dp[i-1][j - weight[i]] + value[i] 是指选择第i件物品，将前i-1 物品 放入 容量为 j - weight[i] 背包的价值 再加上 第i件物品的价值。
  • 此时 第i件已经放入了 ，故为 dp[i-1] [j - weight[i]] + value[i]。 因为01背包(每个物品都只选一次) ！！

完全背包：

dp[i][j] = max(dp[i-1][j], dp[i][j - weight[i]] + value[i])

• dp[i][j - weight[i]] + value[i] 是指 第i件物品是可以重复存放的。
• 含义：存放当前物品（第i件物品）时，重量为j-weight[i]的最大价值 再加上 当前物品的价值。

总结： 是否可重复包含第i件物品。

• dp[i-1][j - weight[i]] + value[i]: 不能重复包含第i件物品 — 01背包
• dp[i][j - weight[i]] + value[i] : 可重复包含第i件物品。 — 完全背包

大师，我悟了！！（悟了一天了）

完全背包的多种写法:

题：

一维数组

为什么完全背包 遍历背包容量是正序，而01背包是逆序

正序是从0~bagsize，dp[j] = Math.max(dp[j],dp[j-w[i]]+v[i]);

• dp[j]总是依赖于 前面的值。 如：

dp[1] = Math.max(dp[1],dp[1-w[i]]+v[i]);  w[0]=1  w[1] =3 即： dp[1] = dp[0]+v[0] = 15 
dp[2] = Math.max(dp[2] ,dp[2-w[i]]+ v[i]); w[0]=1  w[1] =3 即：dp[2] = dp[1]+v[0] = 30 ；
1
2

• 此时dp[2] 又重复了一次 物品0， 说明正序开始 是会重复计算的，故完全背包是正序；

• 若逆序（先计算dp[2],再计算dp[2-w[i]]），则每次比较，dp[j-w[i]] 一直是0。不会重复计算；故01背包需要逆序。

   /**
     * 物品为：
     *
     *       重量   价值
     * 物品0   1       15
     * 物品1   3       20
     * 物品2   4       30
     * 每件商品都有无限个！
     *
     * 问背包能背的物品最大价值是多少？
     */
    /**
     * 1. dp[j] 背包容量为j 可装下的最大价值
     * 2. dp[j] = max(dp[j],dp[j-w[i]]+v[i])
     * 3. 初始化
     * 重复背包
     */
    public static int bagproblem(int[]w , int[]v , int bagsize ){
        int[] dp = new int[bagsize+1];
        for (int i = 0; i < w.length; i++) {
            for (int j = w[i]; j <=bagsize ; j++) {
                dp[j] = Math.max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[bagsize];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

一维数组遍历先后顺序交换

若遍历顺序相交换(先背包容量，再物品个数)，发现结果不变。（单纯完全背包问题这样做是没有影响的。）
只是 遍历方式不同。
代码随想录 |背包问题理论基础完全背包

//    遍历顺序翻转
    public static int bagproblemReverse(int[]w , int[]v , int bagsize ){
        int[] dp = new int[bagsize+1];
            for (int j = 0; j <=bagsize ; j++) {
                for (int i = 0; i < w.length; i++) {
                    if (j>=w[i]){
                        dp[j] = Math.max(dp[j],dp[j-w[i]]+v[i]);
                    }
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[bagsize];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

二维数组

为什么是 dp[i][j-w[i-1]]+v[i-1] ？ 放开头了。

    //    二维数组
    public static int bagproblemTwo(int[]w , int[]v , int bagsize ){
        int[][] dp = new int[w.length+1][bagsize+1];
            for (int i = 1; i <= w.length; i++) {
                for (int j = 1; j <=bagsize ; j++) {
                    if (j>=w[i-1]){
                    dp[i][j] = Math.max(dp[i-1][j],
  	/**
      * dp[i][j-w[i-1]]+v[i-1]  而不是 dp[i-1][j-w[i-1]]+v[i-1]
      * dp[i-1] 是指 存放前i-1 物品(只选一次) 最大价值 的基础上 存放了 第i件物品，
      *       此时 第i件已经放入了，因为01背包是不能重复存放的；
      * dp[i]  是指 第i件物品是可以重复存放的，是存放当前物品时，重量为j-w[i-1]的最大价值
      * 因为 可重复拿物品，因此放东西之后，还可以继续放
      */
                            dp[i][j-w[i-1]]+v[i-1]);
                }else {
                    dp[i][j] = dp[i-1][j]; // 表示不加入第i-1个物品
                }
            }
        }
        for (int i = 0; i <=w.length; i++) {
            for (int j = 0; j <=bagsize; j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println(" ");
        }
//        System.out.println(Arrays.toString(dp));
        return dp[w.length-1][bagsize];
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

三维数组

    // 三重循环 物品可重复选择。
    public static  int bagproblemFork(int[]w , int[]v , int bagsize ){

        int [][]dp = new int[w.length+1][bagsize+1];
        for (int i = 1; i <=w.length; i++) {
            for (int j = 1; j <=bagsize; j++) {
                for (int k = 0; k*w[i-1]<=j ; k++) { // 每件物品能放入背包的最多 个数 k。
                    dp[i][j]  =  Math.max(dp[i-1][j],dp[i-1][j-w[i-1]*k]+k*v[i-1]);
                    //                    不装             装
                }
            }
        }
        for (int i = 0; i <=w.length; i++) {
            for (int j = 0; j <=bagsize; j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println(" ");
        }
        return dp[w.length][bagsize];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

对于 dp[i][j] = Math.max(dp[i-1][j],dp[i][j-w[i-1]]+v[i-1])的公式推导：

原文： 算法之动态规划（DP）求解完全背包问题_PRML_MAN的博客-CSDN博客
其他类似的推导：

原文：『 套用完全背包模板 』详解完全背包（含数学推导） - 完全平方数 - 力扣（LeetCode）