完全背包问题

完全背包是背包问题的基础问题之一，和前面介绍的01背包类似，唯一的不同的是每件物品不再是只有一件，而是无限件。

01背包前面已经做了简单的总结。https://blog.csdn.net/u014532901/article/details/79835712

完全背包问题的描述如下:

给定 $n$ 件物品，对于第 $i$ 件物品，其价值为 $v_{i}$ ，重量为 $w_{i}$ ，与此同时还存在一个体积为 $V$ 的背包，每件物品有无限件，求背包能装下的物品的最大价值 $P$ 。

对应的模型为：

$s . t . \sum_{i = 1}^{n} w_{i} * x_{i} <= V, x_{i} \in N$

$m a x P = \sum_{i = 1}^{n} v_{i} * x_{i}$

解法

解法同01背包十分类似，状态转移方程为：

{f i, j = f i - 1, j i f w i > j f i, j = m a x (f i - 1, j, f i, j - w i + v i) i f w i < = j

01背包的状态转移方程是： $f_{i, j} = m a x (f_{i - 1, j}, f_{i - 1, j - w_{i}} + v_{i})$
完全背包的状态转移方程是： $f_{i, j} = m a x (f_{i - 1, j}, f_{i, j - w_{i}} + v_{i})$

$f_{i, j}$ 表示前 $i$ 种物品装进容量为 $j$ 的背包里面获取的最大价值，因此对于第 $i$ 件物品来放进大小为 $j$ 的背包来讲：

如果 $w_{i} > j$ ，那么该物品放不进去，则此时的收益和前 $i - 1$ 件物品放进大小为 $j$ 的背包的最大收益一样，即 $f_{i, j} = f_{i - 1, j}$ ；
若果wi<=j，则该物品可以放进去，但是此时是有两种选择的，即放进去或者不放进去，因此需要评估两种选择的收益大小：
- 将第 $i$ 件物品不放进去：收益为 $f_{i - 1, j}$
- 将第 $i$ 件物品放进去，但是由于第 $i$ 件物品有无限件，同01背包中不一样，我们的上一个状态不仅仅可以是：前 $i - 1$ 件商品放进背包大小为 $j - w_{i}$ 中的最大收益值，还可以更进一步选择更新的状态：前 $i$ 件物品放进大小为 $j - w_{i}$ 的背包中的最大收益值。此时前一个状态是：前 $i - 1$ 件物品放进大小为 $j - w_{i}$ 的背包中。因此将第 $i$ 件物品放入背包的收益是 $f_{i, j - w_{i}} + v_{i}$
- 最后两个方案中最大的收益便是当前的收益

代码和01背包代码类似：


    public static int knapsackProblemCompletion(int[] value, int[] weight, int bagV) {
        int n = value.length;
        int[][] dp = new int[value.length][bagV + 1];
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= bagV; j++) {//注意这里j是从1开始的
                if (weight[i] > j) {
                    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[n - 1][bagV];
    }


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] value = new int[] { 0, 1, 4, 3,6};// 物品的价值
        int[] weight = new int[] { 0, 5, 2, 4, 3};// 物品的重量
        int bagV = 15;// 背包的大小
        System.out.println(knapsackProblemCompletion(value, weight, bagV));
    }

算法的时间复杂度为： $O (N V)$ ，空间复杂度为： $O (N V)$ 。

二维状态数组可以用如下的二维表格表示：

这里写图片描述

空间优化

由前面的状态转移方程我们可以知道， $f_{i, j}$ 的状态只和前一轮的状态 $f_{i - 1, j}$ 和本轮的稍早的某个状态 $f_{i, j - w_{i}}$ 有关，因此可以像01背包问题一样，将二维数组优化为一维滚动数组，优化后空间复杂度降为 $O (V)$ 。


public static int knapsackProblemCompletionOptimization(int[] value, int[] weight, int bagV) {
        int n = value.length;
        int[] dp = new int[bagV+1];
        for (int i = 1; i < n; i++) {
            for (int j = weight[i]; j <= bagV; j++) {
                dp[j] = Math.max(dp[j], dp[j-weight[i]] + value[i]);
            }
        }
        return dp[bagV];
    }

特别注意这里的内部循环的循环顺序：

for (int j = weight[i]; j <= bagV; j++)

状态回溯

有时候我们不仅仅需要找到能到到最优收益值，还需要找到具体的装包方案，我们可以根据状态数组从后往前倒推得出装包方案。


    public static int[] tracbackCompletion(int[][] dp, int[] weight, int bagV) {
        int[] res = new int[weight.length];
        int j = bagV;
        for (int i = weight.length - 1; i >= 1; i--) {
            //从后往前追踪，dp[i][j]要么来自dp[i-1][j]，要么来自dp[i][j-weight[i]]
            while (dp[i][j] != -1 && dp[i][j] != dp[i-1][j]) {
                res[i] += 1;
                j -= weight[i];
            }
        }
        res[0] = dp[0][j] > 0 ? res[0] + 1 : res[0];
        return res;
    }

这里写图片描述

总结

完全背包是背包问题的基础问题问题之一，和01背包非常类似但是也有些许区别。
完全背包和01背包的区别：完全背包的物品是无限的，而01背包的物品只有一件。

两者的状态转移方程为：

01背包的状态转移方程是： $f_{i, j} = m a x (f_{i - 1, j}, f_{i - 1, j - w_{i}} + v_{i})$
完全背包的状态转移方程是： $f_{i, j} = m a x (f_{i - 1, j}, f_{i, j - w_{i}} + v_{i})$