背包问题类型各题总结-acm(41页).doc
-背包问题类型各题总结-acm-第 41 页分组背包：Problem C: 超市购物Time Limit: 1 Sec Memory Limit: 128 MBSUBMIT: 21 Solved: 10SUBMITSTATUSDescription 上次去超市扫荡回来的东西用完了,Staginner又得跑超市一趟，出发前他列了一张购物清单，打算去买K种不同的商品,每种买一件。到了超市，Staginner发现每种商品有N个品牌，每个品牌此商品的价格为Vi，对Staginner的作用值为Wi，他会从这N个品牌里面挑一个品牌买。这时，Staginner突然想起出门时只带了M元钱，又懒得去取钱了，所以不一定能买完K种商品，只好尽可能地让买的东西对自己的总作用值ans最大。Input 多组样例。 第一行两个整数K，M代表Staginner想买的不同种类商品的数目和他带的钱 (0 < K <= 30, 0 < M <= 2000) 以下输入分为K个部分，代表K种商品。 每个部分第一行为一个数字N，代表第k种商品的N个品牌,N不大于10。之后跟着N行，每行两个数字，代表物品的价格Vi和作用值Wi。其中 0 < Vi < M。Output 输出Case #: 最大总作用值，每两个样例之间有一个空行。Sample Input3 100350 60020 70030 800 230 50040 600 160 2002 5002200 1000260 12001280 300Sample OutputCase 1: 1400Case 2: 1300HINT#include<stdio.h>#include<string.h>int bag100100,dp2500,val100100;int main() int k,m,n,i,j,t,cnt=0; while(scanf("%d %d",&t,&m)!=EOF) memset(dp,0,sizeof(dp); memset(val,0,sizeof(val); memset(bag,0,sizeof(bag); for(i=0;i<t;i+) scanf("%d",&n); bagi0=n; for(j=1;j<=n;j+) scanf("%d %d",&bagij,&valij); for(i=0;i<t;i+) for(j=m;j>=0;j-) for(k=1;k<=bagi0;+k) if(bagik<=j) dpj=dpj>(dpj-bagik+valik)?dpj:(dpj-bagik+valik); printf("Case %d: %dn",+cnt,dpm); printf("n"); return 0;RobberiesTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3802 Accepted Submission(s): 1433Problem DescriptionThe aspiring Roy the Robber has seen a lot of American movies, and knows that the bad guys usually gets caught in the end, often because they become too greedy. He has decided to work in the lucrative business of bank robbery only for a short while, before retiring to a comfortable job at a university.For a few months now, Roy has been assessing the security of various banks and the amount of cash they hold. He wants to make a calculated risk, and grab as much money as possible.His mother, Ola, has decided upon a tolerable probability of getting caught. She feels that he is safe enough if the banks he robs together give a probability less than this.InputThe first line of input gives T, the number of cases. For each scenario, the first line of input gives a floating point number P, the probability Roy needs to be below, and an integer N, the number of banks he has plans for. Then follow N lines, where line j gives an integer Mj and a floating point number Pj . Bank j contains Mj millions, and the probability of getting caught from robbing it is Pj .OutputFor each test case, output a line with the maximum number of millions he can expect to get while the probability of getting caught is less than the limit set.Notes and Constraints0 < T <= 1000.0 <= P <= 1.00 < N <= 1000 < Mj <= 1000.0 <= Pj <= 1.0A bank goes bankrupt if it is robbed, and you may assume that all probabilities are independent as the police have very low funds.Sample Input30.04 30.06 30.10 3Sample Output246题意：输入一个数 表示一共多少组数据 输入一个浮点型数表示小偷被抓的几率不超过这个情况下能偷的最多钱 输入一个整形表示多少个银行 输入3组数据 一组2个数 分别是该银行的钱 以及被抓的几率 求小偷不被抓的情况下能偷的最多钱思路： 一开始我是让几率当背包 然后钱做val 但是 这样是错误的 因为几率是浮点型 虽然可以*100变成整形 但是 几率是相乘得出的 而几率当背包无法模拟几率的相乘 由题中数据看 仿佛用几率当背包 然后几率相加 能得到样例中的结果 但是这是错误的思想几率哪有加的啊 所以就要变通一下 把钱当背包 看总共多少钱 把几率当背包 #include<stdio.h>#include<string.h>double val105,x;int wei105;double bag10500000;void _01bag(int v,int m) int i,j; for(i=0;i<v+3;i+) bagi=0; bag0=1; for(i=0;i<m;i+) for(j=v;j>=weii;j-) if(bagj<bagj-weii*(1-vali) bagj=bagj-weii*(1-vali); for(i=v;i>=0;i-) if(bagi>=1-x) printf("%dn",i);break; return;int main() int t,i,m,v; scanf("%d",&t); while(t-) v=0; scanf("%lf %d",&x,&m); for(i=0;i<m;i+) scanf("%d %lf",&weii,&vali); v=v+weii; _01bag(v,m); return 0;I NEED A OFFER!Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 8472 Accepted Submission(s): 3083Problem DescriptionSpeakless很早就想出国，现在他已经考完了所有需要的考试，准备了所有要准备的材料，于是，便需要去申请学校了。要申请国外的任何大学，你都要交纳一定的申请费用，这可是很惊人的。Speakless没有多少钱，总共只攒了n万美元。他将在m个学校中选择若干的（当然要在他的经济承受范围内）。每个学校都有不同的申请费用a（万美元），并且Speakless估计了他得到这个学校offer的可能性b。不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”，他大叫一声。帮帮这个可怜的人吧，帮助他计算一下，他可以收到至少一份offer的最大概率。（如果Speakless选择了多个学校，得到任意一个学校的offer都可以）。Input输入有若干组数据，每组数据的第一行有两个正整数n,m(0<=n<=10000,0<=m<=1000) 后面的m行，每行都有两个数据ai(整型),bi(实型)分别表示第i个学校的申请费用和可能拿到offer的概率。 输入的最后有两个0。Output每组数据都对应一个输出，表示Speakless可能得到至少一份offer的最大概率。用百分数表示，精确到小数点后一位。Sample Input10 30 0Sample Output44.0%HintYou should use printf("%") to print a '%'.只要把大于号写成小于号就哦可了#include<stdio.h>double bag10005;double val1005;int wei1005;double _01bag(int v,int m) int i,j; for(i=0;i<v+3;i+) bagi=1.0; for(i=0;i<m;i+) for(j=v;j>=weii;j-) if(bagj>bagj-weii*vali) bagj=bagj-weii*vali; return bagv;int main() int n,m,i; double y; while(scanf("%d %d",&n,&m) if(m=0&&n=0) break; for(i=0;i<m;i+) scanf("%d %lf",&weii,&y); vali=1-y; y=1-_01bag(n,m); y=y*100; printf("%.1lf%n",y); return 0; 多重背包 hdu2191Input输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。Output对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。Sample Input18 22 100 44 100 2Sample Output400Authorlcy#include<stdio.h>#include<string.h>int val5000,wei5000;int n;int bag105;int _01bag(int m) int i,j; memset(bag,0,sizeof(bag); for(i=0;i<m;i+) for(j=n;j>=vali;j-) if(bagj<bagj-vali+weii) bagj=bagj-vali+weii; return bagn;int main() int m,t,i,j,ge,temp,v,w; scanf("%d",&t); while(t-) scanf("%d %d",&n,&m); j=0; for(i=0;i<m;i+) scanf("%d %d %d",&v,&w,&ge); temp=1; while(ge>temp)/二进制优化 valj=temp*v; weij+=temp*w; ge=ge-temp; temp=temp*2; valj=ge*v; weij+=ge*w; printf("%dn",_01bag(j); return 0;二维背包hdu2159很重要啊FATETime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3051 Accepted Submission(s): 1297Problem Description最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗？Input输入数据有多组，对于每组数据第一行输入n，m，k，s(0 < n,m,k,s < 100)四个正整数。分别表示还需的经验值，保留的忍耐度，怪的种数和最多的杀怪数。接下来输入k行数据。每行数据输入两个正整数a，b(0 < a,b < 20)；分别表示杀掉一只这种怪xhd会得到的经验值和会减掉的忍耐度。(每种怪都有无数个)Output输出升完这级还能保留的最大忍耐度，如果无法升完这级输出-1。Sample Input10 10 1 101 110 10 1 91 19 10 2 101 12 2Sample Output0-11AuthorXhd二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有 一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为ai和 bi。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为wi。费用加了一维，只需状态也加一维即可。设fivu表示前i件物品付出两种代价分别为v和u时可获得的最大价值。状态转移方程就是：fivu=maxfi-1vu,fi-1v-aiu-bi+wi如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量v和u采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。 for(i = 1; i <= M; i+) for(j = 1; j <= S; j+) for(k = 1; k <= K; k+) if(i - bk >= 0) if(di - bkj - 1 + ak >= dij) dij = di - bkj - 1 + ak; if (diS >= N) break; 一开始一点思路都木有 哎 还是参考了人家的代码 啥时候能自己搞定啊3个循环层的排放顺序无关紧要 怎么放 谁在内谁在外都可以另外记住是求所有满足升级情况下的 剩余最大值一开始我求的只是满足的值 没求最大值 WA了 接近10次啊 那叫一个难受啊#include<stdio.h>#include<string.h>int n,m,k,s;int jingyan105,rennai105,bag105105;int _bag() int i,j,t,jieguo=-1; memset(bag,0,sizeof(bag); for(i=0;i<k;i+) for(t=1;t<=s;t+) for(j=rennaii;j<=m;j+) if(bagjt<bagj-rennaiit-1+jingyani) bagjt=bagj-rennaiit-1+jingyani; if(bagjt>=n) jieguo=m-j>jieguo?m-j:jieguo; return jieguo;int main() int i,j; while(scanf("%d %d %d %d",&n,&m,&k,&s)!=EOF) for(i=0;i<k;i+) scanf("%d %d",&jingyani,&rennaii); printf("%dn",_bag(); Piggy-Bank求最小值的背包 hdu1114Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4603 Accepted Submission(s): 2269Problem DescriptionBefore ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The idea behind is simple. Whenever some ACM member has any small money, he takes all the coins and throws them into a piggy-bank. You know that this process is irreversible, the coins cannot be removed without breaking the pig. After a sufficiently long time, there should be enough cash in the piggy-bank to pay everything that needs to be paid. But there is a big problem with piggy-banks. It is not possible to determine how much money is inside. So we might break the pig into pieces only to find out that there is not enough money. Clearly, we want to avoid this unpleasant situation. The only possibility is to weigh the piggy-bank and try to guess how many coins are inside. Assume that we are able to determine the weight of the pig exactly and that we know the weights of all coins of a given currency. Then there is some minimum amount of money in the piggy-bank that we can guarantee. Your task is to find out this worst case and determine the minimum amount of cash inside the piggy-bank. We need your help. No more prematurely broken pigs! InputThe input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing two integers E and F. They indicate the weight of an empty pig and of the pig filled with coins. Both weights are given in grams. No pig will weigh more than 10 kg, that means 1 <= E <= F <= 10000. On the second line of each test case, there is an integer number N (1 <= N <= 500) that gives the number of various coins used in the given currency. Following this are exactly N lines, each specifying one coin type. These lines contain two integers each, Pand W (1 <= P <= 50000, 1 <= W <=10000). P is the value of the coin in monetary units, W is it's weight in grams. OutputPrint exactly one line of output for each test case. The line must contain the sentence "The minimum amount of money in the piggy-bank is X." where X is the minimum amount of money that can be achieved using coins with the given total weight. If the weight cannot be reached exactly, print a line "This is impossible.". Sample Input310 11021 130 5010 11021 150 301 6210 320 4Sample OutputThe minimum amount of money in the piggy-bank is 60.The minimum amount of money in the piggy-bank is 100.This is impossible.题意：一个储钱罐，知道里面硬币的重量，现在提供N种类型的硬币的重量和价格（数目无限），求储钱罐里面最少的价值。 即：求出把背包装满可以获得的最小的价值.唯一的区别就是初始化该题利用了我们的逆向思维，同时要注意该题他的质量是一定的，也就是说背包一定要是满的，刚开始对于这类背包我们令初始值是负无穷，而这题则相反，令初始值是正无穷，每次区最小的数，同时要注意fj-weighti!=inf应为一相等就与背包一定要满的条件相矛盾； 但是这个条件我没有去用 会稍微浪费点时间把 因为要正好填满 所以必须要初始化很大#include<stdio.h>int val600,wei600,bag10005;int _bag(int v,int n) int i,j; for(i=0;i<n;i+) for(j=weii;j<=v;j+) bagj=(bagj-weii+vali)<bagj?(bagj-weii+vali):bagj; / printf("%d ",bagj); / printf("n"); return bagv;int main() int t,i,n,v,e,f,ans; scanf("%d",&t); while(t-) scanf("%d %d",&e,&f); v=f-e; for(i=0;i<v+3;i+) bagi=999999999; bag0=0; scanf("%d",&n); for(i=0;i<n;i+) scanf("%d %d",&vali,&weii); ans=_bag(v,n); if(ans=999999999) printf("This is impossible.n"); else printf("The minimum amount of money in the piggy-bank is %d.n",ans); return 0;“01背包”最优方案总数分析及实现本文为网上复制本人博文<<背包问题“01背包”详解及实现（包含背包中具体物品的求解）>>中已谈过01背包，这里再重写一下01背包的动态规划状态及状态方程： 设背包容量为V，一共N件物品，每件物品体积为Ci，每件物品的价值为Wi1） 子问题定义：Fij表示前i件物品中选取若干件物品放入剩余空间为j的背包中所能得到的最大价值。2） 根据第i件物品放或不放进行决策 (1-1) 最优方案总数这里指物品总价值最大的方案数。 我们设Gij代表Fij的方案总数，那么最总结果应该是GNV。我们初始化G为1，因为对每个Fij至少应该有一种方案，即前i件物品中选取若干件物品放入剩余空间为j的背包使其价值最大的方案数至少为1，因为Fij一定存在。 下面开始分析怎么求Gij。对于01背包来说： 如果Fij=Fi-1j且Fij!=Fi-1j-Ci+Wi说明在状态ij时只有前i-1件物品的放入才会使价值最大，所以第i件物品不放入，那么到状态ij的方案数应该等于i-1j状态的方案数即Gij=Gi-1j； 如果Fij=Fi-1j-Ci+Wi 且Fij!=Fi-1j说明在状态ij时只有第i件物品的加入才会使总价值最大，那么方案数应该等于i-1j-Ci的方案数，即Gij=Gi-1j-Ci； 如果Fij=Fi-1j-Ci+Wi 且Fij=Fi-1j则说明即可以通过状态i-1j在不加入第i件物品情况下到达状态ij，又可以通过状态i-1j-Ci在加入第i件物品的情况下到达状态ij，并且这两种情况都使得价值最大且这两种情况是互斥的，所以方案总数为Gij=Gi-1j-Ci+ Gi-1j。经过上面的分析，得出下述伪代码：cpp view plaincopyprint?1. F0 0 2. F0 0 3. G 1 4. for i 1 to N 5. do for j 1 to V 6. Fij Fi-1j 7. Gij Gi-1j 8. if (j >= Ci) 9. if (Fij < Fi-1j-Ci+Wi) 10. then Fij Fi-1j-Ci+Wi 11. Gij Gi-1j-Ci 12. else if (Fij = Fi-1j-Ci+Wi) 13. then Gij Gi-1j+Gi-1j-Ci 14. return FNV and GNV F0 0 F0 0 G 1 for i 1 to N do for j 1 to V Fij Fi-1j Gij Gi-1j if (j >= Ci) if (Fij < Fi-1j-Ci+Wi) then Fij Fi-1j-Ci+Wi Gij Gi-1j-Ci else if (Fij = Fi-1j-Ci+Wi) then Gij Gi-1j+Gi-1j-Ci return FNV and GNV 上述方法在保存状态F及G时需要O(NV)的空间复杂度，下面我们对空间复制度进行优化。压缩空间复杂度为O(V)Fij与Gij只分别与Fi-1和Gi-1的状态有关，所以我们可以用两个一维数组F和G来替换二维数组F和G。具体思想请看博文<<背
