————— 第二天 —————
————————————
. . . . . . . .
我們回到剛才的題目當中，假設背包的容量是10，有5個商品可供選擇，每個商品的價值和重量如圖所示：
讓我們來計算一下每件物品的性價比，其結果如下：
毫無疑問，此時性價比最高的是物品4，我們把物品4放入背包當中，背包剩余的容量是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("背包最大價值：" + getHighestValue(capacity, weights, values));
}
public static double getHighestValue(int capacity, int[] weights,int[] values){
//創建物品串列并按照性價比倒序
List<Item> itemList = new ArrayList<>();
for(int i=0;i<weights.length;i++){
itemList.add(new Item(weights[i], values[i]));
}
itemList = itemList.stream().sorted(Comparator.comparing(Item::getRatio).reversed()).collect(Collectors.toList());
//背包剩余容量
int restCapacity = capacity;
//當前背包物品的最大價值
double highestValue = 0;
//按照性價比從高到低選擇物品
for(Item item : itemList){
if(item.weight <= restCapacity){
highestValue += item.value;
restCapacity -= item.weight;
}else{
//背包裝不下完整物品時，選擇該件物品的一部分
highestValue += (double)restCapacity/(double)item.weight * item.value;
break;
}
}
return highestValue;
}
static class Item {
private int weight;
private int value;
//物品的性價比
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;
}
}在這段代碼當中，我們借助了靜態內部類Item，從而更方便地記錄性價比、獲取重量和價值資訊、按性價比排序，
仍然給定一個容量是10的背包，有如下三個物品可供選擇：
這一次我們有個條件限制：只允許選擇整個物品，不能選擇物品的一部分，
如果按照貪心演算法的思路，首先選擇的是性價比最高的物品1，那么背包剩余容量是4，再也裝不下其他物品，而此時的總價值是6：
但這樣的選擇，真的能讓總價值最大化嗎？如果我們不選擇物品1，選擇物品2和物品3的話，剩余容量是0，總價值是7：
顯然，7>6，依靠貪心演算法得出的結果，未必是全域最優解，
漫畫：什么是動態規劃？（整合版）
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/340483.html
標籤：其他