public class DP_Knapsack_Norepetition {

    public static void main(String[] args) {

        int w[] = new int[]{6,3,4,2};
        int v[] = new int[]{30,14,16,9};

        int max_w = 10;

        Integer result = dp_knapsack_repitition(w, v, max_w);
        System.out.println("result:" + result);
        System.out.println();
    }

    private static int dp_knapsack_repitition(int[] w, int[] v, int max_w) {
        int value = 0;

        int best_val[][] = new int[max_w + 1][v.length]; // attention: we intend to allow from 0 ~ 10 (11 numbers instead of 10 numbres)

        // initialize the array
        for (int i = 0; i < best_val.length; i++) {
            for (int j = 0; j < best_val[i].length; j++) {
                best_val[i][j] = -1;
            }
        }

        // set the base state -> w = 0
        for (int j = 0; j <best_val[j].length; j++) {
            best_val[0][j] = 0;
        }

        System.out.println("base state: ");
        print2DArray(best_val);

        for (int nowW = 1; nowW < best_val.length; nowW++) {

            for (int itemIndex = 0; itemIndex < w.length; itemIndex++) { // go through each item to try
                // find the best val
                int tmpVal = 0;

                if (w[itemIndex] <= nowW && itemIndex == 0) { // if this is the first item and it is ok to take
                    tmpVal = Math.max( 0, v[itemIndex]);
                }else if (w[itemIndex] <= nowW && itemIndex != 0) {
                    tmpVal = Math.max( best_val[nowW][itemIndex-1], v[itemIndex] + best_val[nowW-w[itemIndex]][itemIndex-1]); // we either pick the current item or not
                }else if (w[itemIndex] > nowW && itemIndex != 0) {
                    tmpVal = best_val[nowW][itemIndex-1]; // if too heavy, then try the next item for this weight limit
                }

                best_val[nowW][itemIndex] = tmpVal;
            } // end of inner for // 真正有意義的是當每一輪都到了最後一個item時，我們才知道在某個限重下，最好的組合是怎樣。（中間都只是輔助資訊）

        } // end of outer for


        System.out.println("final state: ");
        print2DArray(best_val);

        value = best_val[max_w][v.length-1];

        return value;
    }

    private static void print2DArray(int[][] ary){
        for (int i = 0; i < ary.length; i++) {
            for (int j = 0; j < ary[i].length; j++) {
                System.out.printf("%3d" , ary[i][j]);
            }
            System.out.println();
        }
    }
}