完全背包 初学篇「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

关于更多背包的内容可以在我的“背包”类别中查看

一、题目

有 ｎ 种物品和一个容量为 ｍ 的背包,每种物品都有无限件可用。放入第 i 种物品的费用是 ｖ i ,价值是 W i 。求解:将哪些物品装入背包,可使这些物品的耗费的费用总和不超过背包 容量,且价值总和最大。

二、基本思路

完全背包和０１背包的不同之处就是在于，０１背包每个物品只有一件，而完全背包每个物品有无限件。我们还是以二维数组来进行思考，我们在０１背包中每次更新值时面临的决策是要不要放第ｉ件物品，而在完全背包，我们需要抉择的便是，我们此时要放第ｉ件物品几件？（０——最多能放的件数）

状态转移方程:F[i,j]=max{F[i-1,j],F[i-1,j-k*wi]+k*vi}

总的复杂度可以认为是 O(mn ∑ni=0m/vi \sum_{i=0}^n m/vi ) 这个复杂度是非常大的，我们还要改进这个复杂度。

三、简单的优化

若两件物品 i , j 满足 v i ≤ v j且 w i ≥ w j ,则将可以将物品 j 直接去掉,不用考虑。这个优化方式并不能满足最坏的情况，或许部分题目可以用这个优化卡过时间，故在此处并不做过多描述。

四、更好的优化

考虑到第 i 种物品最多选 m/v i 件,于是可以把第 i 种物品转化为 m /v i 件费用及价值均不变的物品,然后求解这个 01 背包问题。而这样不并不能优化太多的复杂度。 这时我们可以通过二进制的思想再次进行优化，通过几件相同的物品捆绑在一起，再相加我们可以得到每一个值（比如，此时我们第一件物品（就叫他ａ）我们最多可以放５件，那么我们把几个ａ捆绑一下，第一份就一个ａ，第二份两个ａ，第三份四个ａ。我们就可以发现这几份之间互相组合是一定可以完成１－５件ａ放入背包的情况的遍历的）这样一来就把每种物品拆成 O(log ⌊V /C i ⌋) 件物品,是一个很大的改进。 当然这依然不是最好的优化，我们依然不采用。

五、O(V N ) 的算法

还是以０１背包的方向入手，０１背包我们最终优化到的方法是使用一维数组，我们在进行遍历的时候是从后往前遍历的，为什么？我们比较的是还没装入此物品的状态，所以说，从后往前可以防止数据变化，而这个时候我们不就需要让数据变化起来吗，我们需要的就是已经选入第ｉ件物品的子结果，（比如我们比较的是是不是要放两个第一件物品，我们要比较的是什么？是放入一件第一件物品的价值和放两件第一件物品的价值）所以这个时候我们只需要把第二个循环从前往后遍历就可以了。

CODE:

#include<cstdio>
#include<algorithm>
using namespace std;
int w[300],c[300],f[300010];
int V,n;
int main()
{
    scanf("%d%d",&V,&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&w[i],&c[i]);
    }
    for(int i=1; i<=n; i++)
        for(int j=w[i]; j<=V; j++)//注意此处，与0-1背包不同，这里为顺序，0-1背包为逆序
            f[j]=max(f[j],f[j-w[i]]+c[i]);
    printf("max=%d\n",f[V]);
    return 0;
}

复制

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/150680.html原文链接：https://javaforall.cn