————— 第二天—————
————————————
. . . . . . . .
讓我們回到剛才的主題，假設背包的容量為10，并且有五個項目可供選擇，每個項目的價值和重量如圖所示：
我們來計算每件商品的成本效益，結果如下：
毫無疑問，此時成本效益最高的是項目4，我們把項目4放進背包裡，背包剩餘容量是8：
我們選擇項目1放在背包裡，背包的剩餘容量是4：
是以我們選擇了0.8件5件放在背包裡，背包的剩餘容量是0：
public static void main（String[] args） {
int 容量 = 10;
int[] 權重 = {4，6，3，2，4};
int[] 值 = {9，3，1，6，4};
System.out.println （"Backpack Max Value： "getHighestValue （capacity， weights， values））;
}
公共靜态雙精度 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;
目前背包物品的最大價值
雙精度最高值 = 0;
從高到低成本效益中選擇項目
for（項目項目 ： 項目清單）{
if（item.weight <= restCapacity）{
最高值 += 項值;
restCapacity -= item.weight;
}else{
在背面包裝未完成時選擇項目的一部分
最高值 += （雙倍）restCapacity / （double）item.weight * item.value;
休息;
傳回最高值;
靜态類項 {
私人整數重量;
私有整數值;
商品的成本效益
私人雙倍比率;
公共項目（整數權重，整數值）{
這個重量= 重量;
this.value = value;
這個比率 = （雙倍）值 / （雙倍）重量;
public double getRatio（） {
回報率;
在此代碼中，我們使用靜态内部類 Item 來更輕松地記錄成本效益、擷取權重和價值資訊以及對成本效益進行排序。
仍然有一個可容納10人的背包，有三個項目可供選擇：
這次我們有一個條件限制：隻允許選擇整個項目，而不是項目的一部分。
如果按照貪婪的思維算法，第一選擇是成本效益最高的物品1，那麼背包的剩餘容量是4，沒有其他物品可以裝載，此時的總價值是6：
但這樣的選擇真的能最大化總價值嗎？如果我們不選擇項目 1、項目 2 和項目 3，則剩餘容量為 0，總值為 7：
顯然，7>6，依賴于貪婪的算法結果，不一定是全局最優解。
對于01背包問題，我們可以用動态規劃算法來解決，有興趣的小夥伴可以微信搜尋"程式員小灰"，有一個動态規劃算法的解釋。