完全背包问题

Kubrnete 等级 109 1 0

问题描述

有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背包从体积大的开始遍历,这样的话就不能一件物品多次放置。而完全背包是从体积最小的开始遍历,这样的话就会出现一件物品多次放置的特点。这样也就凸显了两种背包的不同,但是这两种都是最基本的背包雏形。

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

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

本文转自 https://blog.csdn.net/guanguandaren/article/details/107960802,如有侵权,请联系删除。

预览图
收藏
评论区