国土网站建设自查报告,邮箱登录,南京服装网站建设,班级网站建设组织机构问题背景#xff1a;
有一天#xff0c;阿里巴巴赶着一头毛驴上山砍柴。砍好柴准备下山时#xff0c;远处突然出现一股烟尘#xff0c;弥漫着直向上空飞扬#xff0c;朝他这儿卷过来#xff0c;而且越来越近。靠近以后#xff0c;他才看清原来是一支马队#xff0c;他…问题背景
有一天阿里巴巴赶着一头毛驴上山砍柴。砍好柴准备下山时远处突然出现一股烟尘弥漫着直向上空飞扬朝他这儿卷过来而且越来越近。靠近以后他才看清原来是一支马队他们共有四十人一个个年轻力壮、行动敏捷。一个首领模样的人背负沉重的鞍袋从丛林中一直来到那个大石头跟前喃喃地说道“芝麻开门吧”随着那个头目的喊声大石头前突然出现一道宽阔的门路于是强盗们鱼贯而入。阿里巴巴待在树上观察他们直到他们走得无影无踪之后才从树上下来。他大声喊道“芝麻开门吧”他的喊声刚落洞门立刻打开了。他小心翼翼地走了进去一下子惊呆了洞中堆满了财物还有多得无法计数的金银珠宝有的散堆在地上有的盛在皮袋中。突然看见这么多的金银财富阿里巴巴深信这肯定是一个强盗们数代经营、掠夺所 积累起来的宝窟。为了让乡亲们开开眼界见识一下这些宝物他想一种宝物只拿一个如果太重就用锤子凿开但毛驴的运载能力是有限的怎么才能用驴子运走最大价值的财宝分给穷人呢 阿里巴巴陷入沉思中……
问题分析
假设山洞中有 n 种宝物每种宝物有一定重量 w 和相应的价值 v毛驴运载能力有限 只能运走 m 重量的宝物一种宝物只能拿一样宝物可以分割。那么怎么才能使毛驴运走宝物的价值最大呢 每次选取单位重量价值最大的宝物也就是说每次选择性价比价值/重量最高的宝物如果可以达到运载重量 m那么一定能得到价值最大
算法设计
1数据结构及初始化。将 n 种宝物的重量和价值存储在结构体 back包含重量、价 值、性价比 3 个成员中同时求出每种宝物的性价比也存储在对应的结构体 back中将其按照性价比从高到低排序。采用 sum 来存储毛驴能够运走的最大价值初始化为 0。 2根据贪心策略按照性价比从大到小选取宝物直到达到毛驴的运载能力。每次选 择性价比高的物品判断是否小于 c毛驴运载能力如果小于 c则放入sum已放入物品的价值加上当前宝物的价值c减去放入宝物的重量如果不小于 c则取该宝物的一部分 c* proportion[i]c0程序结束。c减少到 0则 sum 得到最大值。
在性价比排序的基础上进行贪心算法运算。如果剩余容量比当前宝物的重量大则可 以放入剩余容量减去当前宝物的重量已放入物品的价值加上当前宝物的价值。如果剩余容量比当前宝物的重量小表示不可以全部放入可以切割下来一部分正好是剩余容量然后令剩余容量乘以当前物品的单位重量价值已放入物品的价值加上该价值即为能放入宝物的最大价值。
测试数据
输入 6 19 //宝物数量驴子的承载重量 2 8 //第 1 个宝物的重量和价值 6 1 //第 2 个宝物的重量和价值 7 9 4 3 10 2 3 4
输出 24.6
代码如下
#include iostream
#includestdio.h
#includealgorithm
using namespace std;struct back{double weight;//重量double value;//价值double proportion;//性价比
}a[999];bool beyond(back a,back b){return a.proportion b.proportion;//性价比由大到小排序
}int main()
{int number;//珠宝的种类double sum0.0;//总价值double c;//驴最大载重量cinnumberc;for(int i0;inumber;i){//以次输入数据scanf(%lf,a[i].weight);scanf(%lf,a[i].value);a[i].proportion a[i].value / a[i].weight;}sort(a,anumber,beyond);//按性价比由大到小排序for(int j0;jnumber;j){if(ca[j].weight){//宝物的重量小于或等于驴的载重量c-a[j].weight;//装上该宝物之后驴的剩余载重量suma[j].value;//宝物的价值}else{//宝物的重量大于驴的载重量sum c * a[j].proportion;//分割宝物break;}}printf(%.1lf\n,sum);coutsum;return 0;
}
