有 n 件物品，每件重 wi，價(jià)值為 vi，且每件物品可以進(jìn)行分割，
分割后的價(jià)值按取走重量占該物品總重量的比值計(jì)算。在不超過最大
承載量 C 的范圍內(nèi)，問最大可以取走的價(jià)值為多少？

    本題在最優(yōu)裝載問題的基礎(chǔ)上，增加了價(jià)值項(xiàng)，所以不能想最優(yōu)裝載問題先選出較輕的。根據(jù)本題的特殊性，我們可以任意地對(duì)某一部品進(jìn)行分割，所以我們優(yōu)先選擇性價(jià)比高的物品即可。

    什么是性價(jià)比？舉個(gè)例子，就好比再買菜的時(shí)候，對(duì)于一樣的菜（品種、質(zhì)量都一樣）我們希望買到更便宜的。A店10元3斤，B店7元2斤，那么我們會(huì)決定在A店買。這樣元和斤都不同的情況下看起來似乎不是很好比較，那我們?cè)谟?jì)算的時(shí)候先計(jì)算出單價(jià)，也就是每斤的價(jià)錢，A店大約3.33元一斤，B店3.5元一斤，這樣就可以很輕松的做出選擇了。

//C++

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
struct bag {
    int w,v; //w表示重量 v表示價(jià)值
    double p; //用來儲(chǔ)存v/w 性價(jià)比
}a[10005];
bool cmp(bag x,bag y) {
    return x.p > y.p; //性價(jià)比高的物品排在前面
}
int main() {
    int n,c;
    cin>>n>>c; //輸入物品件數(shù)n和最大承載力t
    for(int i = 0; i < n; i++){
        cin>>a[i].w; //輸入n個(gè)物品的重量
    }
    for(int i = 0; i < n; i++){
        cin>>a[i].v; //輸入n個(gè)物品的價(jià)值
        a[i].p = (double)a[i].v/a[i].w; //計(jì)算每個(gè)物品的性價(jià)比
    }
    sort(a,a+n,cmp); //對(duì)性價(jià)比進(jìn)行排序
    double ans = 0.0;
    for(int i = 0; i < n && t; i++) { //循環(huán)條件要附加上c承載力有剩余
        if(c >= a[i].w) { //可以完全選擇該物品
            ans += a[i].v; //取走該物品的全部?jī)r(jià)值
            c -= a[i].w; //承載力減掉物體重量
        }
        else { //剩余承載力不足以取走全部的該物品
            ans += t*a[i].p; //按照性價(jià)比進(jìn)行分割
            c = 0; //承載力無剩余
        }
    }
    printf('%.2f\n', ans); //輸出答案
    return 0;
}

    在計(jì)算性價(jià)比的時(shí)候要注意一下，在C++中 int/int = int 這樣是無法計(jì)算出小數(shù)的。

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