0-1 Knapsack problem

Java code:

import java.util.LinkedList;
import java.util.List;

class Item {
    int price;
    int weight;
    int pricePerWeight;
    
    public Item(int price, int weight, int pricePerWeight) {
        this.price = price;
        this.weight = weight;
        this.pricePerWeight = pricePerWeight;
    }
}

public class KnapsackProblem {
    static Item[] allItem =
        {new Item(20, 2, 10), new Item(30, 5, 6), new Item(35, 7, 5),
         new Item(12, 3, 4), new Item(3, 1, 3)};
    static int limitWeight = 9;
    static int nowPrice = 0;
    static int nowWeight = 0;
    static int maxPrice = Integer.MIN_VALUE;
    static List<Integer> takeItems = new LinkedList<Integer>();
    static List<Integer> maxPriceTakeItems = new LinkedList<Integer>();
    
    public static void main(String[] args) {
        stealItem(0);
        System.out.print("要拿的物品: ");
        for (int index: maxPriceTakeItems)
            System.out.print(index + 1 + " ");
        System.out.println("\n最大價值: " + maxPrice);
    }

    private static void stealItem(int itemIndex) {
        if (nowWeight <= limitWeight) {
            int boundPrice;
            
            if (nowPrice > maxPrice) {
                maxPrice = nowPrice;
                maxPriceTakeItems.clear();
                for (int index: takeItems)
                    maxPriceTakeItems.add(index);
            }
            boundPrice = calBound(itemIndex);
            if (boundPrice > nowPrice && maxPrice < boundPrice) {
                for (int i=itemIndex; i<allItem.length; i++) {
                    nowPrice += allItem[itemIndex].price;
                    nowWeight += allItem[itemIndex].weight;
                    takeItems.add(itemIndex);
                    stealItem(i + 1);
                    nowPrice -= allItem[itemIndex].price;
                    nowWeight -= allItem[itemIndex].weight;
                    takeItems.remove(takeItems.size() - 1);
                }
            }    
        }
    }

    private static int calBound(int itemIndex) {
        int thePrice = nowPrice;
        int theWeight = nowWeight;
        int i;
        
        for (i=itemIndex; i<allItem.length && theWeight<=limitWeight; i++) {
            thePrice += allItem[i].price;
            theWeight += allItem[i].weight;
        }
        i--;
        thePrice -= allItem[i].price;
        theWeight -= allItem[i].weight;
        return thePrice + allItem[i].pricePerWeight * (limitWeight - theWeight);
    }
}

範例輸入輸出:

---

0-1背包問題就是解決在物品沒有辦法被分割且背包負重有限的情況下能帶走物品的最大價值。程式裡的類別Item就是代表物品，裡面的field有price(價值), weight(重量), 還有pricePerWeight(單位重量的價值)，allItem陣列裡面放的是所有的物品(我偷偷地把它們依照單位重量的價值排序好了XD)。程式的作法就是不斷地拿物品和放物品來找到最大價值，重點是有幾種情況就可以知道物品不要再往下拿了。第一種情況就是總重量已經超過背包的負重，第二種情況就是未來可以拿到的最大價值(利用單位重量的價值計算)等於現在的價值，第三種情況就是未來可以拿到的最大價值比現在已經拿到的最大價值還要少。

因為此程式是解決課本第5章的第33題，所以輸入參數已經是寫死的，輸出為最後拿的物品和最大總價值。