問題背景：

有一天，阿里巴巴趕著一頭毛驢上山砍柴。砍好柴準備下山時，遠處突然出現一股煙塵，彌漫著直向上空飛揚，朝他這兒卷過來，而且越來越近。靠近以后，他才看清原來是一支馬隊，他們共有四十人，一個個年輕力壯、行動敏捷。一個首領模樣的人背負沉重的鞍袋，從叢林中一直來到那個大石頭跟前，喃喃地說道：“芝麻，開門吧！”隨著那個頭目的喊聲，大石頭前突然出現一道寬闊的門路，于是強盜們魚貫而入。阿里巴巴待在樹上觀察他們，直到他們走得無影無蹤之后，才從樹上下來。他大聲喊道：“芝麻，開門吧！”他的喊聲剛落，洞門立刻打開了。他小心翼翼地走了進去，一下子驚呆了，洞中堆滿了財物，還有多得無法計數的金銀珠寶，有的散堆在地上，有的盛在皮袋中。突然看見這么多的金銀財富，阿里巴巴深信這肯定是一個強盜們數代經營、掠奪所
積累起來的寶窟。為了讓鄉親們開開眼界，見識一下這些寶物，他想一種寶物只拿一個，如果太重就用錘子鑿開，但毛驢的運載能力是有限的，怎么才能用驢子運走最大價值的財寶分給窮人呢？ 阿里巴巴陷入沉思中……

問題分析：

假設山洞中有 n 種寶物，每種寶物有一定重量 w 和相應的價值 v，毛驢運載能力有限，
只能運走 m 重量的寶物，一種寶物只能拿一樣，寶物可以分割。那么怎么才能使毛驢運走寶物的價值最大呢？
每次選取單位重量價值最大的寶物，也就是說每次選擇性價比（價值/重量）最高的寶物，如果可以達到運載重量 m，那么一定能得到價值最大

算法設計：

（1）數據結構及初始化。將 n 種寶物的重量和價值存儲在結構體 back（包含重量、價
值、性價比 3 個成員）中，同時求出每種寶物的性價比也存儲在對應的結構體 back中，將其按照性價比從高到低排序。采用 sum 來存儲毛驢能夠運走的最大價值，初始化為 0。
（2）根據貪心策略，按照性價比從大到小選取寶物，直到達到毛驢的運載能力。每次選
擇性價比高的物品，判斷是否小于 c（毛驢運載能力），如果小于 c，則放入sum（已放入物品的價值）加上當前寶物的價值，c減去放入寶物的重量；如果不小于 c，則取該寶物的一部分 c* proportion[i]，c=0，程序結束。c減少到 0，則 sum 得到最大值。

在性價比排序的基礎上，進行貪心算法運算。如果剩余容量比當前寶物的重量大，則可
以放入，剩余容量減去當前寶物的重量，已放入物品的價值加上當前寶物的價值。如果剩余容量比當前寶物的重量小，表示不可以全部放入，可以切割下來一部分（正好是剩余容量），然后令剩余容量乘以當前物品的單位重量價值，已放入物品的價值加上該價值，即為能放入寶物的最大價值。

測試數據：

輸入：
6 19 //寶物數量，驢子的承載重量
2 8 //第 1 個寶物的重量和價值
6 1 //第 2 個寶物的重量和價值
7 9
4 3
10 2
3 4

輸出：
24.6

代碼如下：

#include <iostream>
#include<stdio.h>
#include<algorithm>
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 sum=0.0;//總價值double c;//驢最大載重量cin>>number>>c;for(int i=0;i<number;i++){//以次輸入數據scanf("%lf",&a[i].weight);scanf("%lf",&a[i].value);a[i].proportion = a[i].value / a[i].weight;}sort(a,a+number,beyond);//按性價比由大到小排序for(int j=0;j<number;j++){if(c>=a[j].weight){//寶物的重量小于或等于驢的載重量c-=a[j].weight;//裝上該寶物之后，驢的剩余載重量sum+=a[j].value;//寶物的價值}else{//寶物的重量大于驢的載重量sum+= c * a[j].proportion;//分割寶物break;}}printf("%.1lf\n",sum);cout<<sum;return 0;
}