*本篇讲述一些可以根据背包的思路解决的一些例题。
如对01背包、多重背包、完全背包等不理解的同学请参考前几篇博客~
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2546
题目描述：
电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。
/*变向01背包，因为卡上钱数大于5就可以买东西,题目要求是钱花的越多越好，所以先将最贵的留到最后当钱数为5的时候去购买，那么就变成了v=余额m-5的01背包问题*/ #include<stdio.h>int a[1010][1010];int fmax(int a,int b){ return a>b?a:b;}int main(){ int i,j,n,m,t;int b[1010];while(~scanf("%d",&n),n){ a[0][0]=0; i=1;j=1; for(i=1;i<=n;i++) scanf("%d",&b[i]); scanf("%d",&m); for(i=1;i<n;i++) //b[i+1]为最贵的菜，等到最后买。 if(b[i]>b[i+1]) { t=b[i];b[i]=b[i+1];b[i+1]=t;} for(i=1;i<n;i++) //这里i<n而不是i<=n，因为不算最贵的菜 for(j=0;j<=m-5;j++) //先腾出5元的空间留着买最贵的 {if(j-b[i]>=0) //01背包 a[i][j]=fmax(a[i-1][j],a[i-1][j-b[i]]+b[i]); else a[i][j]=a[i-1][j];}if(m>=5) //如果m的值大于5，才能买菜扣钱，否则不能买菜，m等于本身 m=m-a[i-1][j-1]-b[n];printf("%d\n",m);}return 0;}题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1114
题目描述：
给出小猪钱罐的重量和装满钱后的重量，然后是几组数据，每组数据包括每种钱币的价值与重量，要求出重量最少能装满钱罐时的最大价值
/*标准完全背包，只不过求的是存钱罐里最少的钱数只要把max改成min就可以，完全背包就是每种物品可以取无数次这样对于每一个物品，他的最高价值都没有尽头，所以只能用完全取代来做*/ #include<stdio.h>int min(int a,int b){ return a>b?b:a;}int main(){ int t,e,f,n,v; int p[10000],w[10000],dp[10000]; int i,j; int max=99999999; //自定义最大值 scanf("%d",&t); while(t--) { scanf("%d%d",&e,&f); v=f-e; //v为容量 scanf("%d",&n); for(i=0;i<n;i++) scanf("%d%d",&p[i],&w[i]); for(i=1;i<=v;i++) dp[i]=max; //因为最小解是最优解，所以初始都要变成最大值 for(i=0;i<n;i++) //外层循环仍然是数量n for(j=w[i];j<=v;j++) //内层循环仍然是重量v dp[j]=min(dp[j],dp[j-w[i]]+p[i]); //当第一个物品进入时，dp[j]就进行优质取代 //每到一个可以减去一个w[i]时，就会判断是否选择用状态转移方程，当第i个物品进入时， //还是用这个数组依次进行优质取代判断，所以这里是一维数组，但是时间方面会更耗费 if(dp[v]==max) //如果等于max，那么就是一个没有改变过的空间，那么是不可能存在的 printf("This is impossible.\n"); elseprintf("The minimum amount of money in the piggy-bank is %d.\n",dp[v]); } return 0; }题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1203
题目描述：
Speakless很早就想出国，现在他已经考完了所有需要的考试，准备了所有要准备的材料，于是，便需要去申请学校了。要申请国外的任何大学，你都要交纳一定的申请费用，这可是很惊人的。Speakless没有多少钱，总共只攒了n万美元。他将在m个学校中选择若干的（当然要在他的经济承受范围内）。每个学校都有不同的申请费用a（万美元），并且Speakless估计了他得到这个学校offer的可能性b。不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”，他大叫一声。帮帮这个可怜的人吧，帮助他计算一下，他可以收到至少一份offer的最大概率。（如果Speakless选择了多个学校，得到任意一个学校的offer都可以）。
/*变向01背包，因为被选中的概率有很多种情况，所以先算他没被选中的概率，再减，这样就是求最小价值的背包问题了*/ #include<stdio.h>double dp[1020][1020];double fmin(double a,double b){ return a<b?a:b;}int main(){ double b[1020]; int a[1020]; int i,m; int n,j; while(~scanf("%d%d",&n,&m)){ if(n==0&&m==0) break;for(i=1;i<=m;i++){ scanf("%d%lf",&a[i],&b[i]); b[i]=1.0-b[i]; //把选上的概率变成没被选上的概率 }for(i=0;i<=n;i++)dp[0][i]=1; //如果没申请的话没被选上的概率是100%，也就是1 for(i=1;i<=m;i++){for(j=0;j<=n;j++){if(j-a[i]>=0)dp[i][j]=fmin(dp[i-1][j],dp[i-1][j-a[i]]*b[i]);//状态转移方程，概率是相乘的关系 else dp[i][j]=dp[i-1][j]; }}dp[m][n]=1-dp[m][n]; //dp[m][n]是没被选上的最小值，用1减去也就是选上的最大值了 dp[m][n]*=100;printf("%.1lf%%\n",dp[m][n]);}return 0;}题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2189
题目描述：
灾区来了n位志愿者，抗震救灾指挥部需要将他们分为若干个小组，小组的数量不限，但是要求每个小组的人数必须为素数，请问我们有几种分组的方法呢？
#include<stdio.h>#include<math.h>#include<string.h>int a[160];void sushu() //打表素数 { int i,j; for(i=2;i<=150;i++) for(j=2;j<=sqrt(i);j++) if(i%j==0) { a[i]=1; continue;}//for(i=2;i<=150;i++)//if(!a[i])//printf("%d~~~",i);}int dp[160];void fdp() //打表dp{ /*采用完全背包的思想，把质数看作物品，150看作容纳量 */ memset(dp,0,sizeof(dp)); int i,j; dp[0]=1; //当i物品是质数本身时需+1，故dp[0]=1 for(i=2;i<=150;i++) //外层循环物品 if(!a[i]) //如果为质数进行循环赋值 for(j=0;j+i<=150;j++) //内层循环容纳量 dp[j+i]+=dp[j]; //这里用DP叠加可选择的方案数 }int main(){ int c,n; sushu(); fdp(); scanf("%d",&c); while(c--) { scanf("%d",&n); printf("%d\n",dp[n]); } return 0;}