今天上午系统性地对“0-1背包”问题做了针对性的题目，已经大概明白基本思路了，所以做个小总结。
本篇总结大部分内容引用自博客：http://blog.csdn.net/libin56842/article/details/9338841
1. 0-1背包题目背景：
有
N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
从这个题目中可以看出，01背包的特点就是：
每种物品仅有一件，可以选择放或不放。最终要使得总价值最大。
其状态转移方程是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
对于这方方程其实并不难理解，方程之中，现在需要放置的是第i件物品，这件物品的体积是c[i],价值是w[i],因此
f[i-1][v]代表的就是不将这件物品放入背包，而f[i-1][v-c[i]]+w[i]则是代表将第i件放入背包之后的总价值，比较两者的价值，得出最大的价值存入现在的背包之中。
理解了这个方程后，将方程代入实际题目的应用之中，可得
<pre name="code" class="cpp">for(i = 1; i<=n; i++) { for(j = v; j>=c[i]; j--)//在这里，背包放入物品后，容量不断的减少，直到再也放不进了 { f[i][v]=max(f[i-1][v],f[i-1][v-c[i]]+w[i]); } }
2. 例题分析：
（1）HDU-2546：饭卡
题目源地址：http://acm.hdu.edu.cn/showproblem.php?pid=2546
很经典的一道01背包题，要注意的是这里只要剩余的钱不低于5元，就可以购买任何一件物品，所以5在这道题中是很特许的，再使用01背包之前，我们首先要在现在所拥有的余额中保留5元，用这五元去购买最贵的物品，而剩下的钱就是背包的总容量，可以随意使用，因此可得代码：
//HOJ--2546:饭卡 0-1背包
#include<iostream>
#include<algorithm>
#include<memory.h>
using namespace std;
int cmp(int a,int b)
{
return a<b;
}
int main()
{
int n,m;
int price[1010],dp[1010];
int i,j;
while(cin>>n && n)
{
for(i=1;i<=n;i++)
cin>>price[i];
cin>>m;
memset(dp,0,sizeof(dp));
sort(price+1,price+1+n,cmp);
int MAX=price[n];
if(m<5)//低于5元不能购买
{
cout<<m<<endl;
continue;
}
m=m-5;//取出5元用于购买最贵的物品
for(i=1;i<n;i++)//01背包
{
for(j=m;j>=price[i];j--)
dp[j]=max(dp[j],dp[j-price[i]]+price[i]);
}
int ans=m+5-dp[m]-MAX;
cout<<ans<<endl;
}
return 0;
}
（2）HDU-1171：Big Event in HDU
题目源地址：http://acm.hdu.edu.cn/showproblem.php?pid=1171
这道题咋看有点复杂，其实也只是换了一种思维，因为题目要求要尽量平均分配，所以我们可以先将总价值sum求出，然后得出其分配的平均值为sum/2,要注意这个答案可能为小数，但是又因为sum是整数，所以最后得出的sum/2是要小于等于实际的值。将这个结果进行01,背包，可以得出其中一个宿舍所得的最大价值，而另一个宿舍的最大价值也可以相应的得到，而前者必定小于等于后者。
<pre name="code" class="cpp">//HOJ--1171:Big Event in HDU #include<iostream> #include<algorithm> #include<memory.h> using namespace std; int val[5005]; int dp[255555]; int main() { int n,sum; int i,j,a,b,k; while(cin>>n && n>0) { memset(val,0,sizeof(val)); memset(dp,0,sizeof(dp)); k=0; sum=0; for(i=0;i<n;i++) { cin>>a>>b; while(b--) { val[k++]=a;//将价值存入数组 sum=sum+a; } } for(i=0;i<k;i++) { for(j=sum/2;j>=val[i];j--) dp[j]=max(dp[j],dp[j-val[i]]+val[i]); } cout<<sum-dp[sum/2]<<" "<<dp[sum/2]<<endl; } return 0; }
（3）HDU-2602：Bone Collector
题目源地址：http://acm.hdu.edu.cn/showproblem.php?pid=2602
最经典最简单的0-1背包问题。
//HOJ--2602:Bone Collector
#include<iostream>
#include<memory.h>
#include<algorithm>
using namespace std;
int main()
{
int caseNum,N,V;
int value[1010],volume[1010],dp[10000];
int i,j;
cin>>caseNum;
while(caseNum--)
{
cin>>N>>V;
memset(value,0,sizeof(value));
memset(volume,0,sizeof(volume));
memset(dp,0,sizeof(dp));
for(i=1;i<=N;i++)
cin>>value[i];
for(i=1;i<=N;i++)
cin>>volume[i];
for(i=1;i<=N;i++)
{
for(j=V;j>=volume[i];j--)
dp[j]=max(dp[j],dp[j-volume[i]]+value[i]);
}
cout<<dp[V]<<endl;
}
return 0;
}<span style="color:#ff0000;">
</span>
（4）HDU-2955：Robberies
题目源地址：http://acm.hdu.edu.cn/showproblem.php?pid=2955
分析：
1、抢n个银行，不被抓，是每次都不被抓，用乘法原理处理每次不被抓的概率。
2、转化为0 1 背包：将所有银行的总钱数当做背包的容积v，将不被抓的概率当做cost[i]，
在一般的0 1背包中都是加上cost[i] ，这里由于是乘法原理，所以应该是转化为乘法。
这样，传统的01背包累加问题变成了垒乘。
3、状态转移方程：dp[j]=max(dp[j],dp[j-bank[i].money]*bank[i].run)
dp[j]表示抢j钱时的最大不被抓概率。
//HOJ--2955:Robberies
#include<iostream>
#include<memory.h>
using namespace std;
struct node
{
int money;
float run;//不被抓的概率
}bank[110];
float dp[11000];
int main()
{
int caseNum,N,sum;
float risk,limit;
int i,j;
cin>>caseNum;
while(caseNum--)
{
cin>>limit>>N;
limit=1.00-limit;//最大被抓概率转化为最小不被抓概率
sum=0;
for(i=1;i<=N;i++)
{
cin>>bank[i].money>>risk;
bank[i].run=1.00-risk;//转化为不被抓的概率
sum=sum+bank[i].money;
}
memset(dp,0,sizeof(dp));
dp[0]=1.00;//不抢钱被抓概率为0
for(i=1;i<=N;i++)//抢i银行的钱
{
for(j=sum;j>=bank[i].money;j--)
{
dp[j]=max(dp[j],dp[j-bank[i].money]*bank[i].run);
}
}
for(i=sum;i>=0;i--)//从最大钱数开始枚举
{
if(dp[i]>limit)//找到钱数最大而且能成功逃跑的
{
cout<<i<<endl;
break;
}
}
}
return 0;
}
（5）HDU3466：Proud Merchants
题目源地址：http://acm.hdu.edu.cn/showproblem.php?pid=3466
首先对数组按照（limit-price）进行排序，这样保证差额最小为最优，再进行0-1背包。
//HOJ--3466:Proud Merchants #include<iostream> #include<memory.h> #include<algorithm> using namespace std; struct node { int price; int limit; int value; }item[510]; int cmp(node a,node b)//按limit-price排序，保证差额最小为最优 { return a.limit-a.price < b.limit-b.price; } int main() { int N,money; int dp[5100]; int i,j; while(cin>>N>>money) { for(i=1;i<=N;i++) cin>>item[i].price>>item[i].limit>>item[i].value; memset(dp,0,sizeof(dp)); sort(item+1,item+1+N,cmp); for(i=1;i<=N;i++) { for(j=money;j>=item[i].limit;j--)//剩余的钱大于limit才能买 { dp[j]=max(dp[j],dp[j-item[i].price]+item[i].value); } } cout<<dp[money]<<endl; } return 0; }
（6）HDU1864：最大报销额
问题源地址：http://acm.hdu.edu.cn/showproblem.php?pid=1864
最大报销额这道题有好几种解法。一种是将价格通过乘以100全部化为整数，再利用0-1背包方法解决，简要代码如下：
for(i = 0; i<=l; i++) { for(j = sum; j>=money[i]; j--) dp[j] = max(dp[j],dp[j-money[i]]+money[i]); } printf("%.2lf\n",dp[sum]/100.0);
之前我自己做这道题的时候没用0-1背包，是直接用的DP求最大和，判定条件比0-1背包解法麻烦了点。
具体解题方法可以参照我之前的博客：http://blog.csdn.net/u012856866/article/details/38920889
附上我之前写的代码：
//HOJ--1864:最大报销额 0MS / 284K
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
struct node
{
float value;
}ticket[35];
int cmp(float a,float b)
{
return a > b;
}
int main()
{
int i,j,N,n; //N:发票张数 n:每张发票上物品数
int CanUse[35]; //判断单张发票是否符合要求
char kind,ch; //kind:物品的种类
float sum,val; //sum:总报销值 val:每件物品的价值
float sum_A,sum_B,sum_C; //单类物品的总金额
while(cin>>sum>>N && N)
{
for(i=0;i<N;i++)
{
CanUse[i]=1;
ticket[i].value=0;
cin>>n;//输入每张发票上物品件数
sum_A=sum_B=sum_C=0.00;
for(j=0;j<n;j++)
{
cin>>kind>>ch>>val;
if(kind!='A' && kind!='B' && kind!='C')//注意：只有A，B,C三类可以报销
CanUse[i]=0;
else
{
if(kind=='A') sum_A=sum_A+val;
else if(kind=='B') sum_B=sum_B+val;
else if(kind=='C') sum_C=sum_C+val;
}
ticket[i].value=ticket[i].value+val;
}
if(sum_A>600.00 || sum_B>600.00 || sum_C>600.00)//每张发票上单类物品价值不可超过600
CanUse[i]=0;
if(ticket[i].value>1000.00 || ticket[i].value>sum)//每张发票价值不可超过1000元 且每张发票总金额不可超过总报销额
CanUse[i]=0;
}
float t[35];
int len=0;
for(i=0;i<N;i++)
{
if(CanUse[i])
{
t[len]=ticket[i].value;
len++;
}
}
sort(t,t+len,cmp);//排序函数一定要有，不然上述提到的测试数据会出错！
//这里最大钱数应该要用动态规划来求，dp[n]=max(dp[n-1]+t[n],t[n]),限制条件为各值都要小于总报销值sum
float dp[35];//动态规划数组
dp[0]=t[0];
for(i=1;i<len;i++)
{
if(dp[i-1]+t[i]>=t[i])
{
if(dp[i-1]+t[i]<=sum)
dp[i]=dp[i-1]+t[i];
else dp[i]=max(dp[i-1],t[i]);//这里也很关键！
}
else
{
dp[i]=ticket[i].value;//ticket[i].value>sum CanUse[i]=0保证了单张发票总额不会超过sum
}
}
//找出dp[]中的最大值
float max_value=0.00;
for(i=0;i<len;i++)
{
if(dp[i]>max_value)
max_value=dp[i];
}
printf("%.2lf\n",max_value);
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/163007.html
