0-1背包问题(二维数组压缩为一维数组)

悠悠 2024-03-26 20:09 47阅读 0赞

0-1背包不懂的，可以看这篇  
[https://donglin.blog.csdn.net/article/details/129412502][https_donglin.blog.csdn.net_article_details_129412502]

### 一维dp数组 ###

对于背包问题其实状态都是可以压缩的。  
在使用二维数组的时候，递推公式：dp\[i\]\[j\] = max(dp\[i - 1\]\[j\], dp\[i - 1\]\[j - weight\[i\]\] + value\[i\]);  
把dp\[i - 1\]这一层拷贝到dp\[i\]上，不如只用一个一维数组了，只用dp\[j\]  
dp\[j\] = max(dp\[j\], dp\[j - weight\[i\]\] + value\[i\]);

### 动态规划 ###

**动规五部曲分析如下：**

*  1.确定dp数组的定义

在一维dp数组中，dp\[j\]表示：容量为j的背包，所背的物品价值可以最大为dp\[j\]。

*  2.一维dp数组的递推公式

dp\[j\]可以通过dp\[j - weight\[i\]\]推导出来，dp\[j - weight\[i\]\]表示容量为j - weight\[i\]的背包所背的最大价值。  
dp\[j - weight\[i\]\] + value\[i\] 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。  
此时dp\[j\]有两个选择，一个是取自己dp\[j\] 相当于 二维dp数组中的dp\[i-1\]\[j\]，即不放物品i，一个是取dp\[j - weight\[i\]\] + value\[i\]，即放物品i，指定是取最大的，毕竟是求最大价值

递推公式

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

*  3.一维dp数组如何初始化

dp\[j\]表示：容量为j的背包，所背的物品价值可以最大为dp\[j\]，那么dp\[0\]就应该是0，因为背包容量为0所背的物品的最大价值就是0。

*  4.一维dp数组遍历顺序

假设用正序的话,这个时候第一个数是求的f\[0\], 一直求到了第f\[10\], 那么你这个时候再去调用f\[10-weight\].f\[10-weight\]肯定是在f\[10\]前面,也就是已经被更改了, 因为排在10前面的数肯定已经被第i层的循环动过了,也就是说这个数据并不是上一轮的数据了,要是还原成二维递归式, 就变成了dp\[i\]\[j\]=max(dp\[i\]\[j\],dp\[i\]\[j-weight\]+value),这明显是不对的,但是如果逆序的话,先求f\[10\],那么就会调用f\[10-weight\],因为这个时候f\[10-weight\]肯定还没有被改过,也就是说这个数肯定是上一轮的数据.

*  5.举例推导dp数组

![在这里插入图片描述][39d273fb46614de3b62821697d6bce8b.png]  
代码

public static void main(String[] args) {
        
            int[] weight = {
        1, 3, 4};
            int[] value = {
        15, 20, 30};
            int bagWight = 4;
            testWeightBagProblem(weight, value, bagWight);
        }
    
        public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
        
            int wLen = weight.length;
            //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
            int[] dp = new int[bagWeight + 1];
            //遍历顺序：先遍历物品，再遍历背包容量
            for (int i = 0; i < wLen; i++){
        
                for (int j = bagWeight; j >= weight[i]; j--){
        
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                }
            }
            //打印dp数组
            for (int j = 0; j <= bagWeight; j++){
        
                System.out.print(dp[j] + " ");
            }
        }

![在这里插入图片描述][d82faea27bfc44ffbd3afed73d8763a8.png]

[https_donglin.blog.csdn.net_article_details_129412502]: https://donglin.blog.csdn.net/article/details/129412502
[39d273fb46614de3b62821697d6bce8b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/e4d8efa4a3374ef0b95d431a0ab8b763.png
[d82faea27bfc44ffbd3afed73d8763a8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/8b262d78e4114c1b913496d96f300f08.png