《连续背包问题算法设计.docx》由会员分享，可在线阅读，更多相关《连续背包问题算法设计.docx（7页珍藏版）》请在三一文库上搜索。
1、连续背包问题算法设计题目：已知有n种物品和一个可容纳M重量的背包，每种物品i的重量为wi。假定将物品i的一部分xi放入背包就会得到pi*xi的效益，这里，0=xi0。采用怎样的装包方法才会使装入背包物品的总效益最大呢？显然，由于背包容量是M，因此，要求所有选中要装入背包的物品总重量不得超过M。如果这n件物品的总重量不超过M，则把所有物品装入背包自然获得最大效益。如果这些物品重量的和大于M，则在这种情况下该如何包装呢？问题形式描述如下：极大化sum(pi*xi)(i=1.n)约束条件sum(wixi)=M(i=1.n)0=xi0,wi0(i=1.n)解题要求：Input有多次测试，每次测试如下：
2、输入第一行n,M分别代表物品数目和背包容量，然后有n行的输入每行输入wi,pi,分别代表物品i的重量和得到效益能力Output每次测试输出如下：输出第一行最大效益和此时背包容纳的重量接下来一行输出n个数xi，表示第i种物品所取的百分比注意：所有输出取2位有效小数，每次测试输出一个空行Sample Input3 2018 2515 2410 150 0Sample Output31.50 20.000.00 100% 50.00%解题思路：（1）由题意可以看出我们应该尽量选pi大而且wi小的物品，因此我们可以以pi/wi作为量度标准（2）按量度标准将物品以降序排序（3）从前往后搜索上述序列，直到
3、物品取完或背包放满位置代码设计：#include#include#include#includeusing namespace std;#defineBAGMAXNUM 10000#define PRECISION 1e-6typedef struct tagBAGint n;/number of bagdouble w;/weight of bagdouble p;/profit of bagdouble r;/result of p/wdouble x;/rate of weightBAG;BAG bagsBAGMAXNUM;double M;int cmp(const void *a,c
4、onst void *b)/compare for descending by result of p/wBAG c=*(BAG*)a;BAG d=*(BAG*)b;if(c.r-d.rPRECISION)return -1;return 1;int cmp1(const void *a,const void *b)/compare for ascending by bag numberBAG c=*(BAG*)a;BAG d=*(BAG*)b;return c.nd.n?1:-1;void print(int n)int i=0;printf(%.2lf%,bagsi.x*100);for(
5、i+;inM)if(n=0)break;profit=sum=0;for(i=0;in;i+)scanf(%lf%lf,&bagsi.w,&bagsi.p);bagsi.r=bagsi.p/bagsi.w;bagsi.n=i+1;bagsi.x=0;profit+=bagsi.p;sum+=bagsi.w;if(sumM)/select allprintf(%.2lf %.2lfn,profit,sum);printf(100%);i=0;for(i+;in;i+)printf( 100%);printf(nn);continue;qsort(bags,n,sizeof(bags0),cmp);/sort descending by p/wprofit=sum=0;i=0;while(in&sumM)bagsi.x=(M-sum)/bagsi.w;elsebagsi.x=1;sum+=bagsi.w*bagsi.x;profit+=bagsi.p*bagsi.x;i+;qsort(bags,n,sizeof(bags0),cmp1);/sort ascending by bag numberprintf(%.2lf %.2lfn,profit,sum);print(n);return 0;