有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

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

2:f[v]=max(f[v],f[v-c[i]]+w[i]);

完全背包面臨的不是對于第i件物品選不選的問題了而是選多少件了問題了。。。所以f[v]的當(dāng)前狀態(tài)允許由當(dāng)前狀態(tài)推得。

實現(xiàn)方法有是那種

1：o(n*v)

這里正確理解這句經(jīng)典的話很關(guān)鍵（引用）：

換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時，依據(jù)的是一個絕無已經(jīng)選入第i件物品的子結(jié)果f[i-1][v-c[i]]。而現(xiàn)在完全背包的特點恰是每種物品可選無限件，所以在考慮“加選一件第i種物品”這種策略時，卻正需要一個可能已選入第i種物品的子結(jié)果f[i][v-c[i]]，所以就可以并且必須采用v=0..V的順序循環(huán)。這就是這個簡單的程序為何成立的道理。

http://acm.hdu.edu.cn/showproblem.php?pid=1114

View Code #include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 10007
#define inf 9999999
int c[N],w[N],f[N];

int main()
{
int t,n,i,j,V;
int s,e;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&s,&e);
V=e-s;
for(i=1;i<=V;i++)
f[i]=inf;
f[0]=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",&w[i],&c[i]);
for(i=1;i<=n;i++)
{
for(j=c[i];j<=V;j++)
f[j]=min(f[j],f[j-c[i]]+w[i]);
}
if(f[V]!=inf)
printf("The minimum amount of money in the piggy-bank is %d.\n",f[V]);
else
printf("This is impossible.\n");

}
return 0;
}

2:轉(zhuǎn)化成01背包每種物品是一個01背包的方法：

View Code #include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int max_s = 100007;
const int inf = 9999999;
int c[max_s],w[max_s],f[max_s];
int main()
{
int i,j,k,n,m,V,t,num;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
V=m-n;
scanf("%d",&num);
for(i=0;i<num;i++)
scanf("%d%d",&w[i],&c[i]);
f[0]=0;
for(i=1;i<=V;i++)
f[i]=inf;
for(i=0;i<num;i++)
{
for(j=1;j<=V/c[i];j++)
{
for(k=V;k>=c[i];k--)
f[k]=min(f[k],f[k-c[i]]+w[i]);
}
}
if(f[V]!=inf)
printf("The minimum amount of money in the piggy-bank is %d.\n",f[V]);
else
printf("This is impossible.\n");
}
return 0;
}

3：利用二進制思想；

把第i種物品拆成費用為c[i]*2^k、價值為w[i]*2^k的若干件物品，其中k滿足c[i]*2^k<=V。這是二進制的思想，因為不管最優(yōu)策略選幾件第i種物品，總可以表示成若干個2^k件物品的和。這樣把每種物品拆成O(log V/c[i])件物品，是一個很大的改進。（本人不大理解望大牛指點）未發(fā)現(xiàn)實現(xiàn)代碼。。求解。。

轉(zhuǎn)載于:https://www.cnblogs.com/E-star/archive/2011/12/06/2278244.html

總結(jié)

以上是生活随笔為你收集整理的背包学习————完全背包的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。