完全背包问题

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

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

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

给定 n n 件物品，对于第ii件物品，其价值为 vi v i ，重量为 wi w i ，与此同时还存在一个体积为 V V 的背包，每件物品有无限件，求背包能装下的物品的最大价值PP。

对应的模型为：

s.t.  ∑ni=1 wi∗xi<=V,xi∈N s . t .     ∑ i = 1 n   w i ∗ x i <= V , x i ∈ N

maxP=∑ni=1vi∗xi m a x P = ∑ i = 1 n v i ∗ x i

解法

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

{fi,j=fi−1,jif wi>jfi,j=max(fi−1,j,fi,j−wi+vi) if wi<=j { 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背包的状态转移方程是： fi,j=max(fi−1,j,fi−1,j−wi+vi) f i , j = m a x ( f i − 1 , j , f i − 1 , j − w i + v i ) 完全背包的状态转移方程是： fi,j=max(fi−1,j,fi,j−wi+vi) f i , j = m a x ( f i − 1 , j , f i , j − w i + v i )

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

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

代码和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(NV) O ( N V ) ，空间复杂度为： O(NV) O ( N V ) 。

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

空间优化

由前面的状态转移方程我们可以知道， fi,j f i , j 的状态只和前一轮的状态 fi−1,j f i − 1 , j 和本轮的稍早的某个状态 fi,j−wi f i , j − w i 有关，因此可以像01背包问题一样，将二维数组优化为一维滚动数组，优化后空间复杂度降为 O(V) 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背包的状态转移方程是： fi,j=max(fi−1,j,fi−1,j−wi+vi) f i , j = m a x ( f i − 1 , j , f i − 1 , j − w i + v i ) 完全背包的状态转移方程是： fi,j=max(fi−1,j,fi,j−wi+vi) f i , j = m a x ( f i − 1 , j , f i , j − w i + v i )