亚洲av永久无码天堂网,久久精品人人做人人爽电影蜜月

[導(dǎo)讀]—————?第二天?—————————————————........我們回到剛才的題目當(dāng)中，假設(shè)背包的容量是10，有5個(gè)商品可供選擇，每個(gè)商品的價(jià)值和重量如圖所示：讓我們來計(jì)算一下每件物品的性價(jià)比，其結(jié)果如下：毫無疑問，此時(shí)性價(jià)比最高的是物品4，我們把物品4放入背包當(dāng)中，背包剩...

—————? 第二天? —————

————————————

. . . . . . . .

我們回到剛才的題目當(dāng)中，假設(shè)背包的容量是10，有5個(gè)商品可供選擇，每個(gè)商品的價(jià)值和重量如圖所示：

讓我們來計(jì)算一下每件物品的性價(jià)比，其結(jié)果如下：

毫無疑問，此時(shí)性價(jià)比最高的是物品4，我們把物品4放入背包當(dāng)中，背包剩余的容量是8：

我們選擇物品1放入背包，背包剩余的容量是4：

于是，我們選擇0.8份的物品5放入背包，背包剩余的容量為0：

????public?static?void?main(String[]?args)?{
????????int?capacity?=?10;
????????int[]?weights?=?{4,6,3,2,5};
????????int[]?values?=?{9,3,1,6,5};
????????System.out.println("背包最大價(jià)值："? ?getHighestValue(capacity,?weights,?values));
????}

????public?static?double?getHighestValue(int?capacity,?int[]?weights,int[]?values){

????????//創(chuàng)建物品列表并按照性價(jià)比倒序
????????List?itemList?=?new?ArrayList<>();
????????for(int?i=0;i????????????itemList.add(new?Item(weights[i],?values[i]));
????????}
????????itemList?=?itemList.stream().sorted(Comparator.comparing(Item::getRatio).reversed()).collect(Collectors.toList());

????????//背包剩余容量
????????int?restCapacity?=?capacity;
????????//當(dāng)前背包物品的最大價(jià)值
????????double?highestValue?=?0;

????????//按照性價(jià)比從高到低選擇物品
????????for(Item?item?:?itemList){
????????????if(item.weight?<=?restCapacity){
????????????????highestValue? =?item.value;
????????????????restCapacity?-=?item.weight;
????????????}else{
????????????????//背包裝不下完整物品時(shí)，選擇該件物品的一部分
????????????????highestValue? =?(double)restCapacity/(double)item.weight?*?item.value;
????????????????break;
????????????}
????????}

????????return?highestValue;
????}

????static?class?Item?{
????????private?int?weight;
????????private?int?value;
????????//物品的性價(jià)比
????????private?double?ratio;

????????public?Item?(int?weight,?int?value){
????????????this.weight?=?weight;
????????????this.value?=?value;
????????????this.ratio?=?(double)value?/?(double)weight;
????????}

????????public?double?getRatio()?{
????????????return?ratio;
????????}
????}