完全背包

100 阅读 0 评论 66 点赞

我是靠谱客的博主个性大炮，最近开发中收集的这篇文章主要介绍完全背包，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题：

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

基本思路

这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解 01背包时的思路，令f[i][j]表示前i种物品恰放入一个容量为c的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：

f[i][j]=max{f[i-1][j-k*w[i]]+k*v[i]|0<=k*c[i]<=v}

这跟01背包问题一样有O(VN)个状态需要求解，但求解每个状态的时间已经不是常数了，求解状态f[i][v]的时间是O(v/c[i])，总的复杂度可以认为是O(V*Σ(V/c[i]))，是比较大的。

将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。但我们还是试图改进这个复杂度。

其中F[i-1][j-k*w[i]]+k*v[i]表示前i-1种物品中选取若干件物品放入剩余空间为j-k*w[i]的背包中所能得到的最大价值加上k件第i种物品的总价值；

设物品种数为n，背包容量为c，第i种物品体积为w[i]，第i种物品价值为v[i]。

代码1：

#include<queue>
#include<stack>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int dp[1001][1001];
int w[1001];
int v[1001];
int main()
{
int n,c;
while(scanf("%d%d",&n,&c)!=EOF)
{
int i,j;
memset(dp,0,sizeof(dp));
for(i=1; i<=n; i++)
scanf("%d",&w[i]);
for(i=1; i<=n; i++)
scanf("%d",&v[i]);
for(i=1; i<=n; i++)
{
for(j=0; j<=c; j++)
{
for(int k=0; k*w[i]<=j; k++)
dp[i][j]=max(dp[i][j],dp[i-1][j-k*w[i]]+k*v[i]);//表示前i-1种物品中选取若干件物品放入剩余空间为j-k*w[i]的背包中所能得到的最大价值加上k件第i种物品的总价值；
}
}
printf("%dn",dp[n][c]);
}
return 0;
}

简单优化：筛选

这个筛选过程如下：先找出体积大于背包的物品直接筛掉一部分（也可能一种都筛不掉），然后筛选出同体积但价值大的物品，其余的都筛掉（这也可能一件都筛不掉）即若两件物品满足w[i] ≤w[j]&&v[i] ≥v[j]时将第j种物品直接筛选掉。因为第i种物品比第j种物品物美价廉，用i替换j得到至少不会更差的方案。

转化为01背包：

因为同种物品可以多次选取，那么第i种物品最多可以选取c/w[i]件价值不变的物品，然后就转化为01背包问题。整个过程的时间复杂度并未减少。

如果把第i种物品拆成体积为w[i]×2k价值v[i]×2k的物品，其中满足w[i]×2k≤V。那么在求状态F[i][j]时复杂度就变为O(log2(V/C[i]))。整个时间复杂度就

变为O(NVlog2(c/w[i]))

将原始算法的DP思想转变一下。

设F[i][j]表示出在前i种物品中选取若干件物品放入容量为j的背包所得的最大价值。那么对于第i种物品的出现，我们对第i种物品放不放入背包

进行决策。如果不放那么F[i][j]=F[i-1][j]；如果确定放，背包中应该出现至少一件第i种物品，所以F[i][j]种至少应该出现一件第i种物品,

即F[i][j]=F[i][j-w[i]]+v[i]。为什么会是F[i][j-w[i]]+v[i]？因为我们前面已经最大限度的放了第i件物品,如果能放就放这最后的一件,

（或者理解为前面已经往背包中放入了第i件物品，我们每一次只增加一件的往背包里放,而且只能增加一件,多了放不下）

代码2：

#include<stack>
#include<queue>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[1010][1010];
int w[1010];
int v[1010];
int main()
{
int n,c;
while(scanf("%d%d",&n,&c)!=EOF)
{
memset(dp,0,sizeof(dp));
int i,j;
for(i=1; i<=n; i++)
scanf("%d",&w[i]);
for(i=1; i<=n; i++)
scanf("%d",&v[i]);
for(i=1; i<=n; i++)
{
for(j=0; j<=c; j++)
{
if(j>=w[i])
dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);//注意此处与0-1背包的不同，0-1背包：max(dp[i-1][j],dp[i-1][j-w[i]+v[i])
else
dp[i][j]=dp[i-1][j];
}
}
printf("%dn",dp[n][c]);
}
return 0;
}

一维解法：

和01背包问题一样，完全背包也可以用一维数组来保存数据。算法样式和01背包的很相似，唯一不同的是对V遍历时变为正序，而01背包为逆序

。01背包中逆序是因为F[i][]只和F[i-1][]有关，且第i件的物品加入不会对F[i-1][]状态造成影响。而完全背包则考虑的是第i种物品的出现的问题，

第i种物品一旦出现它势必应该对第i种物品还没出现的各状态造成影响。也就是说，原来没有第i种物品的情况下可能有一个最优解，现在第i种物品

出现了，而它的加入有可能得到更优解，所以之前的状态需要进行改变，故需要正序。

代码：

#include<stack>
#include<queue>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[1010];
int w[1010];
int v[1010];
int main()
{
int n,c;
while(scanf("%d%d",&n,&c)!=EOF)
{
int i,j,k;
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
for(i=1;i<=n;i++)
{
for(j=w[i];j<=c;j++)//注意此处与0-1背包的不同，0-1为倒序(j=c;j>=w[i];j--)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
printf("%dn",dp[c]);
}
return 0;
}

感谢大佬http://blog.csdn.net/howardemily/article/details/55223039