完全背包问题 - HelloWorld开发者社区

问题描述

有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背包问题的两篇文章。