完全背包问题

问题描述

有n种物品和一个容量为c的背包，每种物品都就可以选择任意多个，第i种物品的价值为v[i]，体积为w[i]，求解：在不超过背包容量的情况下，选择放入哪些物品能够使得背包中的价值最大？

跟01背包一样，完全背包也是一个很经典的动态规划问题，不同的地方在于01背包问题中，每件物品最多选择一件；而在完全背包问题中，只要背包装得下，每件物品可以选择任意多件。从每件物品的角度来说，与之相关的策略已经不再是选或者不选了，而是有取0件、取1件、取2件...直到取⌊c/wi⌋（[ ]表示向下取整）件。

在上一篇文章中，我们提到过01背包问题的递推关系：

认识01背包问题之后，现在让我们来看对于完全背包问题的递归解法：

完全背包的递推关系

我们用V_total(i,j)表示前i种物品放入一个容量为j时的背包获得的最大价值，那么对于第i种物品，我们有k种选择,0 <= k * w[i] <= j,(容量约束条件）即可以选择0、1、2...k件第i种物品，所以递推表达式为：

V_total(i,j) = max{V_total(i-1, j - w[i] * k) + v[i] * k}; （0 <= k * w[i] <= j）

（注：当k=0则为不选，最多可选k=j/w[i]件。在这个范围中找出k种选择种的最优解）

现在我们很容易能够写出对应的递归代码。

理所当然地，我们将用一个数组存储计算结果，如果递归时已经计算过，那么返回该结果。

 int V_total(int i, int j)
 {
     int value = 0;
     if (i && j) //可选物品个数和初始容量皆不为0
     { 
         if (j < w[i])
             value = V_total(i - 1, j);
         else
             for (int k = 0; k * w[i] <= j; k++)
             {
                 int temp = V_total(i - 1, j - w[i] * k) + v[i] * k;
                 value = temp > value ? temp : value;
             }
     }
     return value;
 }

填表法

当然，有了这个递推关系式，其实也是我们的状态转移方程式，现在我们可以尝试用填表的方式自下而上处理。

比如只有两个物品：物品A：价值5，体积5，物品B：价值8：体积7，背包容量为10，下面开始填表。

物品1重量V=5，价值P=5，物品2重量V=7，价值P=8。可选物品个数为0和容量为0的选择都为0。

i=1时，若t<10，背包最多只能放下1个物品1，价值为5；当t=10时，能放下2个物品1，因此i=1时的最大值为10。

i=2时，若5<=t<7时，背包能放下1个物品1；当7<=t<10时，背包能放下1个物品2，最大值为8；当t=10时，能放下2个物品1或1个物品2，因此最大值为10。通过求解这些子问题的最优解，我们推导出了全局最优解。

转换代码如下

 for (int i = 1; i <= n; i++)
     for (int j = 1; j <= c; j++)
         for (int k = 0; k * w[i] <= j; k++)
             values[i + 1][j] = max(values[i + 1][j], values[i][j - k * w[i]] + k * v[i]);
 cout << values[n][c];

和01背包一样，这里效率仍可以继续优化。具体思路这里就不重复介绍了，可以翻看前面的01背包问题动态规划篇。

优化后的状态转移方程为：

V_total(t) = max{V_total(t), V_total(t - wi) + vi}

附完整代码：

 #include <bits/stdc++.h>
 using namespace std;
 int n, c, d;
 int v[1002], w[1002], dp[1002];
 int main()
 {
 ​
     cin >> n >> c;
     for (int i = 1; i <= n; i++)
         cin >> w[i] >> v[i];
     for (int i = 1; i <= n; i++)
         for (int j = w[i]; j <= c; j++)
             dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
     cout << dp[c];
 }

其实完全背包问题也可以转化成01背包问题来求解：

由于第i件物品最多选 ⌊c/wi⌋(向下取整) 件，可以将第i种物品转化为体积 j=⌊c/wi⌋件价值相同的物品，然后再对这个01背包问题进行求解。具体留给大家自行解决。如果遇到问题，可以翻开前面关于01背包问题的两篇文章。

总结

完全背包问题跟01背包有很多相似之处，比较一下他们的状态转移方程以及各种解法，就会发现他们其实是异父异母的亲兄弟。

(建议仔细思考其中的区别)

它们的本质区别就是01背包从体积大的开始遍历，这样的话就不能一件物品多次放置。而完全背包是从体积最小的开始遍历，这样的话就会出现一件物品多次放置的特点。这样也就凸显了两种背包的不同，但是这两种都是最基本的背包雏形。

这两个背包问题的关键都在于状态转移方程的寻找，如果对于类似的问题没有思路，可以先尝试找出递归解法，然后自上而下的记忆法便水到渠成了。

当然，最重要的还是解题思路，理解记忆法和填表法的精髓，有助于之后举一反三，去解决类似的延伸问题。

最后

以上就是活力抽屉为你收集整理的完全背包问题的全部内容，希望文章能够帮你解决完全背包问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。