JZTXT

完全背包问题

发布时间 2023-09-01 16:21:54作者: tryingWorm

完全背包问题

一.问题描述

背包问题的基本条件

现有(n + 1)种物品，每种物品有无数个，编号由0到n，每种物品有两个属性，质量weight，价值value；有一个背包，容量(最大承受质量)为capacity；

为了描述每一种物品，我们使用w[n + 1]和v[n + 1]来描述，因此描述第i种物品时，我们使用w[i]表示其质量，v[i]表示其价值

现在往背包中装物品，要求所装入物品的质量和不超过capacity，求装入物品的最大价值

说明

由于完全背包问题和01背包问题十分相似，所以在分析的过程中我会与01背包问题进行比较，我对01背包问题请参见01背包问题 - tryingWorm - 博客园 (cnblogs.com)

二.解决方案

背包问题是动态规划的经典题型，我使用Carl哥的动态规划五部曲进行分析。

1.明确dp数组含义

dp[i][j]表示假设有i + 1种物品(编号0 - i)，背包容量为j的情况下，最大的装入物品总价值为dp[i][j]

2.确定递推公式

我尝试使用dp[i][j]前面的状态来推导该状态，由于根据其实际意义，我们发现dp[i][j]只可能是以下两种状态中的一种。

  1. 最后装入的物品不是第i号物品

    与01背包问题相同，这种情况下，问题转换为在物品最多考虑到第i - 1号，背包容量为j时，其获取的最大价值。由前面dp数组的含义知，最大价值为dp[i - 1][j]

  2. 最后装入的物品是第i号物品

    这种情况下，需要先算物品最多考虑到第i号(因为每种物品可能有多个，倒数第二个物品也有可能是第i号物品)，背包容量为j - w[i]时(要留出放最后一个第i号物品的空间)，获取的最大价值为dp[i][j - w[i]]，然后再加上第i号物品的价值v[i]，所以最大价值为dp[i][j - w[i]] + v[i]

然后，我们取这两种情况的最大值即可，即max(dp[i - 1][j], dp[i][j - w[i]] + v[i])

3.确定递推初始化条件

与01背包问题类似的，我们从公式出发，可以发现只要确定了第0行就能推出其他位置的值。根据dp[i][j]的实际意义，我们知道dp[0][j]代表着在只考虑第0号物品，背包容量为capacity的时候可以获取的最大价值。显然，只要统计当前背包容量j可以放下几个0号物品，物品最大价值就是那几个0号物品的价值。

4.确定递推顺序

与01背包问题十分类似，由公式max(dp[i - 1][j], dp[i][j - w[i]] + v[i])，经观察我们发现，dp[i - 1][j]是dp[i][j]正上方的那一个元素，dp[i][j - w[i]]是dp[i][j]那一行左边的元素。所以递推顺序的要求和01背包问题是一样的，只要保证从左到右，从上到下的顺序就行了，先遍历i还是j是无所谓的。递推顺序的图形化理解与01背包相同，参见01背包问题 - tryingWorm - 博客园 (cnblogs.com)

5.举例推导dp数组

这是为了验证公式的正确性，这里省略了

6.实现代码

根据上面的分析，很容易写出以下实现代码

public static int bagComplete(int[] weight, int[] value, int capability){
        int[][] dp = new int[weight.length][capability + 1];
        //初始化
        for(int j = weight[0]; j <= capability; j++){
            dp[0][j] = value[0] * (j / weight[0]);
        }

        //先遍历i，再遍历j
        for(int i = 1; i < weight.length; i++){
            for(int j = 0; j <= capability; j++){
                if(j < weight[i]){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
                }
            }
        }

        //先遍历j，再遍历i
        // for(int j = 0; j <= capability; j++){
        //     for(int i = 1; i < weight.length; i++){
        //         if(j < weight[i]){
        //             dp[i][j] = dp[i - 1][j];
        //         }else{
        //             dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
        //         }
        //     }
        // }

        return dp[weight.length][capability];
    }

三.空间优化

类似于01背包问题，上面的代码中，我们发现时间复杂度已经达到最低O(vn)，(v为背包容量，n为物品数量)，但空间复杂度O(vn)还可以优化。

1.思路

与01背包问题相同，我的思路也是去掉i这一维度，改成通过控制遍历顺序，达到和二维数组相同的效果。

2.递推顺序

通过与01背包类似的分析，我们得出的结论应该是只能先遍历i再遍历j，j顺序遍历。但是，由于还可以由其他公式推出正确结果，我们会发现先遍历j再遍历i，j顺序遍历也是能得出正确结果的。原因分析如下：

先遍历j再遍历i，j顺序遍历的分析

我直接从一维数组的dp出发来思考递推关系式。dp[j]表示背包容量为j时，考虑所有物品情况下的最大价值。可以想到，类似于爬楼梯的思路，想要达成容量为j的最大价值，最后一个放入的物品只能是第0种，第1种，...，第n种，然后取这些情况的最大值就行

假设最后放入的是第i种

此时想要背包物品价值最大，我们只要让背包容量为j - w[i]的时候物品价值最大，然后加上第i个的价值，即dp[j - w[i]] + v[i]

所以，我们可以得出dp[j] = max(dp[j - w[i]] + v[i])，(i从0取到n或者从n取到0)，显然j也必须从小取到大，然后转换成代码，形式上就是先遍历j再遍历i的代码。

ps：01背包问题不能如此思考的原因

在01背包问题的情景下，每一种物品只有一个，而在算dp[j - w[i]]时，根据定义，在达成容量为j - w[i]的最大价值时，我们有可能已经把第i号物品使用了，所以这个公式在01背包中是不成立的

3.初始化

与01背包相同，这里也有两种初始化方法

  1. 方法1

    类似二维数组的初始化方式，将dp[j]中的每一个数初始化为dp[0][j]的值，i从1开始遍历，具体代码见后面的实现代码部分

  2. 方法2

    初始化为"i = -1"的那一行，定义为任何物品都不装的情况下，容量为j的背包的最大价值，显然最大价值为0，此时i从0开始遍历即可

4.实现代码

  1. 使用方法1初始化

    public static int bagComplete1(int[] weight, int[] value, int capability){
        int[] dp = new int[capability + 1];

        //初始化法1
        for(int j = weight[0]; j <= capability; j++){
            dp[j] = value[0] * (j / weight[0]);
        }

        //先遍历i，再遍历j
        for(int i = 1; i < weight.length; i++){
            for(int j = weight[i]; j <= capability; j++){
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }

        //先遍历j，再遍历i
        // for(int j = 0; j <= capability; j++){
        //     for(int i = 1; i < weight.length; i++){
        //         if(j >= weight[i]){
        //             dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        //         }
        //     }
        // }
        return dp[capability];
    }

  2. 使用方法2初始化

    public static int bagComplete2(int[] weight, int[] value, int capability){
        int[] dp = new int[capability + 1];

        //初始化法2
        //初始化dp[-1][j],即在没有物品的情况下，不同背包容量的最大价值，显然都是0

        //先遍历i，再遍历j
        for(int i = 0; i < weight.length; i++){
            for(int j = weight[i]; j <= capability; j++){
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }

        //先遍历j，再遍历i
        // for(int j = 0; j <= capability; j++){
        //     for(int i = 0; i < weight.length; i++){
        //         if(j >= weight[i]){
        //             dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        //         }
        //     }
        // }
        return dp[capability];
    }