@@ -0,0 +1,2133 @@
+package practice.oldschool;%0A%0Aimport java.util.ArrayList;%0A%0A/**%0A * Created by yichen on 10/15/15.%0A *%0A * KnapsackProblem%0A */%0Apublic class KnapsackProblem %7B%0A%0A    private int numbers = 5;%0A    private final String%5B%5D fruits = %7B%22%E6%9D%8E%E5%AD%90%22, %22%E8%98%8B%E6%9E%9C%22, %22%E6%A9%98%E5%AD%90%22, %22%E8%8D%89%E8%8E%93%22, %22%E7%94%9C%E7%93%9C%22%7D;%0A    private final int%5B%5D weights = %7B4, 5, 2, 1, 6%7D;%0A    private final int%5B%5D prices = %7B4500, 5700, 2250, 1100, 6700%7D;%0A%0A    private final int maxWeight = 8;%0A%0A    private int%5B%5D bestValues;%0A    private int%5B%5D bestItems;%0A%0A    private ArrayList%3CInteger%3E result;%0A%0A    public KnapsackProblem() %7B%0A        bestValues = new int%5BmaxWeight+1%5D;%0A        bestItems = new int%5BmaxWeight+1%5D;%0A%0A        for (int i = 0; i %3C numbers; i++) %7B%0A            for (int w = weights%5Bi%5D; w %3C= maxWeight; w++) %7B%0A                int preWeight = w - weights%5Bi%5D;%0A                int newValue = bestValues%5BpreWeight%5D + prices%5Bi%5D;%0A                if (newValue %3E bestValues%5Bw%5D) %7B%0A                    bestValues%5Bw%5D = newValue;%0A                    bestItems%5Bw%5D = i;%0A                %7D%0A%0A            %7D%0A        %7D%0A%0A        int weightLeft = maxWeight;%0A        result = new ArrayList%3C%3E();%0A        while (weightLeft %3E 0) %7B%0A            result.add(bestItems%5BweightLeft%5D);%0A            weightLeft -= weights%5BbestItems%5BweightLeft%5D%5D;%0A        %7D%0A%0A    %7D%0A%0A    private void printResult() %7B%0A        System.out.println(%22Resut: %22);%0A        int totalValue = 0;%0A        for (Integer i : result) %7B%0A            totalValue += prices%5Bi%5D;%0A            System.out.println(fruits%5Bi%5D + %22 $%22 + prices%5Bi%5D + %22, Weight:%22 + weights%5Bi%5D);%0A        %7D%0A        System.out.println(%22Total value: $%22 + totalValue);%0A    %7D%0A%0A    private void printBestTable() %7B%0A        System.out.println(%22Best table: %22);%0A        for (int i = 0; i %3C maxWeight+1; i++) %7B%0A            System.out.print(String.format(%22%255d %22, i));%0A            System.out.print(String.format(%22%255d %22, bestValues%5Bi%5D));%0A            System.out.print(String.format(%22%255d %22, bestItems%5Bi%5D));%0A            System.out.println(fruits%5BbestItems%5Bi%5D%5D);%0A        %7D%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        KnapsackProblem kp = new KnapsackProblem();%0A        kp.printBestTable();%0A        kp.printResult();%0A%0A    %7D%0A%7D%0A

Add KnapsackProblem