package equus.independent.problem;

public class KnapsackProblem {

    public static int solve(int maxWeight, int[] prices, int[] weights) {
        int itemNumber = prices.length;
        int[][] dp = new int[itemNumber + 1][maxWeight + 1];
        // dp[i][w] i番目までのitemからweightの総和がw以下となるように選んだ時のprice合計の最大値

        for (int weightSum = 1; weightSum <= maxWeight; weightSum++) {
            dp[1][weightSum] = weightSum < weights[0] ? 0 : prices[0];
        }
        for (int includingItem = 2; includingItem <= itemNumber; includingItem++) {
            for (int weightSum = 1; weightSum <= maxWeight; weightSum++) {
                if (weightSum < weights[includingItem - 1]) {
                    dp[includingItem][weightSum] = dp[includingItem - 1][weightSum];
                } else {
                    dp[includingItem][weightSum] = Math.max(dp[includingItem - 1][weightSum],
                                    dp[includingItem - 1][weightSum - weights[includingItem - 1]]
                                                    + prices[includingItem - 1]);
                }
            }
        }
        return dp[itemNumber][maxWeight];
    }
}

@@ -110,21 +110,22 @@
 , int%5B%5D 
-price
+weight
 s, int%5B%5D
@@ -125,22 +125,21 @@
 , int%5B%5D 
-weight
+price
 s) %7B%0A   
@@ -251,16 +251,18 @@
  // dp%5Bi
++1
 %5D%5Bw%5D i%E7%95%AA%E7%9B%AE
@@ -307,16 +307,103 @@
 %E5%90%88%E8%A8%88%E3%81%AE%E6%9C%80%E5%A4%A7%E5%80%A4%0A%0A
+        for (int includingItem = 0; includingItem %3C itemNumber; includingItem++) %7B%0A    
         
@@ -415,33 +415,33 @@
 int weightSum = 
-1
+0
 ; weightSum %3C= m
@@ -481,76 +481,717 @@
     
-dp%5B1%5D%5BweightSum%5D = weightSum %3C weights%5B0%5D ? 0 : prices%5B0%5D;%0A        %7D
+    if (weightSum %3C weights%5BincludingItem%5D) %7B%0A                    dp%5BincludingItem + 1%5D%5BweightSum%5D = dp%5BincludingItem%5D%5BweightSum%5D;%0A                %7D else %7B%0A                    dp%5BincludingItem + 1%5D%5BweightSum%5D = Math.max(dp%5BincludingItem%5D%5BweightSum%5D,%0A                                    dp%5BincludingItem%5D%5BweightSum - weights%5BincludingItem%5D%5D + prices%5BincludingItem%5D);%0A                %7D%0A            %7D%0A        %7D%0A        return dp%5BitemNumber%5D%5BmaxWeight%5D;%0A    %7D%0A%0A    public static int solveNoLimit(int maxWeight, int%5B%5D weights, int%5B%5D prices) %7B%0A        int itemNumber = prices.length;%0A        int%5B%5D%5B%5D dp = new int%5BitemNumber + 1%5D%5BmaxWeight + 1%5D;%0A        // dp%5Bi+1%5D%5Bw%5D i%E7%95%AA%E7%9B%AE%E3%81%BE%E3%81%A7%E3%81%AEitem%E3%81%8B%E3%82%89weight%E3%81%AE%E7%B7%8F%E5%92%8C%E3%81%8Cw%E4%BB%A5%E4%B8%8B%E3%81%A8%E3%81%AA%E3%82%8B%E3%82%88%E3%81%86%E3%81%AB%E9%81%B8%E3%82%93%E3%81%A0%E6%99%82%E3%81%AEprice%E5%90%88%E8%A8%88%E3%81%AE%E6%9C%80%E5%A4%A7%E5%80%A4%0A
 %0A   
@@ -1224,9 +1224,9 @@
 m = 
-2
+0
 ; in
@@ -1238,17 +1238,16 @@
 ngItem %3C
-=
  itemNum
@@ -1303,17 +1303,17 @@
 htSum = 
-1
+0
 ; weight
@@ -1398,20 +1398,16 @@
 dingItem
- - 1
 %5D) %7B%0A   
@@ -1431,32 +1431,36 @@
 dp%5BincludingItem
+ + 1
 %5D%5BweightSum%5D = d
@@ -1466,36 +1466,32 @@
 dp%5BincludingItem
- - 1
 %5D%5BweightSum%5D;%0A  
@@ -1541,32 +1541,36 @@
 dp%5BincludingItem
+ + 1
 %5D%5BweightSum%5D = M
@@ -1585,36 +1585,32 @@
 dp%5BincludingItem
- - 1
 %5D%5BweightSum%5D,%0A  
@@ -1660,17 +1660,17 @@
 ingItem 
--
++
  1%5D%5Bweig
@@ -1702,66 +1702,10 @@
 Item
- - 1%5D%5D%0A                                                   
+%5D%5D
  + p
@@ -1727,12 +1727,8 @@
 Item
- - 1
 %5D);%0A

add KnapsackProblem