背包问题总结

2018-02-08 10:24:53来源:oschina作者:小衰哥有点帅人点击

分享
01背包

不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前.


死亡骑士:"我要买道具!"


地精商人:"我们这里有三种道具,血瓶150块一个,魔法药200块一个,无敌药水350块一个."


死亡骑士:"好的,给我一个血瓶."


说完他掏出那张N元的大钞递给地精商人.


地精商人:"我忘了提醒你了,我们这里没有找客人钱的习惯的,多的钱我们都当小费收了的,嘿嘿."


死亡骑士:"......你妹"


死亡骑士想,与其把钱当小费送个他还不如自己多买一点道具,反正以后都要买的,早点买了放在家里也好,但是要尽量少让他赚小费.


现在死亡骑士希望你能帮他计算一下,最少他要给地精商人多少小费.


上面就是一个01背包问题。上面的问题可以描述为:



有n个物品,每个物品的重量为weight[i],每个物品的价值为value[i]。现在有一个背包,它所能容纳的重量为total,问:当你面对这么多有价值的物品时,你的背包所能带走的最大价值是多少?



思路:每个物品无非是装入背包或者不装入背包,那么就一个一个物品陆续放入背包中。可以有



tab[i][j] = max(tab[i-1][j-weight[i]]+value[i],tab[i-1][j]) ({i,j|0


其中i表示放第i个物品,j表示背包所容纳的重量,那么tab[i-1][j-weight[i]]+value[i]表示放入第i物品,刚开始接触会有疑问,tab[i-1][j-weight[i]]这个值,可以这样理解:tab[i-1][j]为装到上一个物品在背包j容量时的最佳值,那么如果我要求在j容量的时候放入现在的i物品的价值,那么是不是要先得到容量为(j-weight[i])时候的价值,即先得到 tab[i-1][j-weight[i]] ,所以 tab[i-1][j-weight[i]]+value[i] 为放入第i物品的价值; tab[i-1][j] 就是不放入第i个物品。


动态规划的思维就在这里体现了,即tab[i-1][j]是tab[i][j]的最优解(我觉得上面的思路讲解较容易理解)。


例子:5个物品,(重量,价值)分别为:(5,12),(4,3),(7,10),(2,3),(6,6)。



故有:


for i=[0,n)
for(j=totle;j>=weight[i]; j--)
tab[j] = max(tab[j-weight[i]]+value[i],tab[j])
/* print tab[0][total] */
完全背包

不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前.


死亡骑士:"我要买道具!"


地精商人:"我们这里有三种道具,血瓶150块无限个,魔法药200块无限个,无敌药水350块无限个."


死亡骑士:"好的,给我一个血瓶."


说完他掏出那张N元的大钞递给地精商人.


地精商人:"我忘了提醒你了,我们这里没有找客人钱的习惯的,多的钱我们都当小费收了的,嘿嘿."


死亡骑士:"......你妹"


死亡骑士想,与其把钱当小费送个他还不如自己多买一点道具,反正以后都要买的,早点买了放在家里也好,但是要尽量少让他赚小费.


现在死亡骑士希望你能帮他计算一下,最少他要给地精商人多少小费.


上面的魔兽场景描述跟上面的只有小小的差异,就是物品有一个变为了无限个,这就是完全背包问题。完全背包问题可以描述为:



有n种物品,每种物品有无限个,每个物品的重量为weight[i],每个物品的价值为value[i]。现在有一个背包,它所能容纳的重量为total,问:当你面对这么多有价值的物品时,你的背包所能带走的最大价值是多少?



有了上面01背包的式子,这题会变的容易理解很多,只是这个式子要有小小的改动。01背包在二维数组上操作,就是为了防止一个物品被放入多次的情况。因此一维数组可以满足完全背包的问题。如下:



tab[j] = max(tab[j-weight[i]]+value[i],tab[j]);({i,j|0


根本就是一样的,只不过物品可以被放多次。


故有:


for i=[0,n)
for(j=weight[i]; j<=total; j++)
tab[j] = max(tab[j-weight[i]]+value[i],tab[j])
/*print tab[0][total]*/ 多重背包

不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前.


死亡骑士:"我要买道具!"


地精商人:"我们这里有三种道具,血瓶150块a个,魔法药200块b个,无敌药水350块c个."


死亡骑士:"好的,给我一个血瓶."


说完他掏出那张N元的大钞递给地精商人.


地精商人:"我忘了提醒你了,我们这里没有找客人钱的习惯的,多的钱我们都当小费收了的,嘿嘿."


死亡骑士:"......你妹"


死亡骑士想,与其把钱当小费送个他还不如自己多买一点道具,反正以后都要买的,早点买了放在家里也好,但是要尽量少让他赚小费.


现在死亡骑士希望你能帮他计算一下,最少他要给地精商人多少小费.


上面的魔兽场景描述跟上面的又有了小小的差异,就是物品有一个变为了有限个,问题也就变成了多重背包问题。


有n种物品,每种物品有amount[i]个,每个物品的重量为weight[i],每个物品的价值为value[i]。现在有一个背包,它所能容纳的重量为total,问:当你面对这么多有价值的物品时,你的背包所能带走的最大价值是多少?



多重和完全更接近,多了数量的限制,用一个count[n]计数数组来限制物品i的数量。当放入第i个物品是较优值的时候,count[i]=count[j-weight[i]]+1(j 的含义请查看代码);这样做是因为,放入第i个物品的操作是基于count[j-weight[i]]放入的,所以当count[i-weight[i]]>=amount[i]时,就要阻止放入即便放入第i个物品是较优值。 故有:


for i=[0,n)
/*将count数组清零 */
for(j=weight[i]; j<=total; j++)
ifcount[j-weight[i]] tab[j] = max(tab[j-weight[i]]+value[i],tab[j]);
iftab[j]=tab[j-weight[i]]+value[i] //决定放入i是较优解
count[i] = count[j-weight[i]] + 1
elseiftab[j]=0//防止装第1个物品和装其他物品的情况
tab[j] = tab[j-1],count[j] = count[j-1]
elsecount[j] = count[j-1]
/*print tab[0][total]*/
相关例题

HDU2546:饭卡 http://acm.hdu.edu.cn/showproblem.php?pid=2546(01背包) 要注意的是这里只要剩余的钱不低于5元,就可以购买任何一件物品,所以5在这道题中是很特许的,


再使用01背包之前,我们首先要在现在所拥有的余额中保留5元,用这五元去购买最贵的物品,


而剩下的钱就是背包的总容量,可以随意使用


#include
#include
using namespace std;
int main()
{
int n;
while(~scanf("%d",&n),n)
{
int i,price[2013]= {0},dp[2013] = {0};
for(i = 1; i<=n; i++)
scanf("%d",&price[i]);
sort(price+1,price+1+n);
int MAX=price[n];
int j,m;
scanf("%d",&m);
if(m<5)//低于5元不能购买
{
printf("%d/n",m);
continue;
}
m-=5;//取出5元用于购买最贵的物品
for(i = 1; i {
for(j = m;j>=price[i];j--)
{
dp[j] = max(dp[j],dp[j-price[i]]+price[i]);
}
}
printf("%d/n",m+5-dp[m]-MAX);
}
return 0;
}

HDU 4508湫湫系列故事——减肥记I


http://acm.hdu.edu.cn/showproblem.php?pid=4508(完全背包)


#include
#include
using namespace std;
int max(int a,int b)
{
if(a>b) return a;
elsereturn b;
}
int main()
{
int n,m;
int a[100005],b[100005],c[100005];
while(scanf("%d",&n)!=EOF)
{
memset(c,0,sizeof(c));
for(int i=0;i scanf("%d%d",&a[i],&b[i]);
scanf("%d",&m);
for(int j=0;j {
for(int k=b[j];k<=m;k++)
{
c[k]=max(c[k-b[j]]+a[j],c[k]);
}
}
printf("%d/n",c[m]);
}
return 0;
}

hdu 2602Bone Collector


http://acm.hdu.edu.cn/showproblem.php?pid=2602(01背包)


注意和上题进行比较。


#include
#include
using namespace std;
int max(int a,int b)
{
if(a>b) return a;
elsereturn b;
}
int main()
{
int T,N,V;
int i,j,k;
int v[1005],w[1005],c[1005];
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&N,&V);
for(i=0;i scanf("%d",&v[i]);
for(i=0;i scanf("%d",&w[i]);
memset(c,0,sizeof(c));
for(i=0;i {
for(j=V;j>=w[i];j--)
{
c[j]=max(c[j],c[j-w[i]]+v[i]);
}
}
printf("%d/n",c[V]);
}
return 0;
}

相关链接点击打开链接

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台