当前位置:   article > 正文

二维数组完全背包与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)

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/weixin_40725706/article/detail/466301
推荐阅读
相关标签
  

闽ICP备14008679号