import java.util.Stack;

public class DP_Knapsack_repetition {

    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]; // attention: we intend to allow from 0 ~ 10 (11 numbers instead of 10 numbres)
        int parent[] = new int[max_w + 1];
        int itemPicked[] = new int[max_w + 1];

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

        // set the base state
        best_val[0] = 0; // when the total allowed weight is zero, of course, the value is zero

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

            // get the max value and weight
            int bestValThisRun = 0; // to decide picking wich item will produce the best value

            for (int itemIndex = 0; itemIndex < w.length; itemIndex++) {
                if (w[itemIndex] <= nowW) { // if less than affordable weight, we pick it as one of the tries
                    int tmpVal = v[itemIndex] + best_val[nowW - w[itemIndex]];
                    if (tmpVal > bestValThisRun) {
                        bestValThisRun = tmpVal;
                        parent[nowW] = nowW - w[itemIndex];
                        itemPicked[nowW] = itemIndex;
                    }
                }
            } // end of for

            // update the best_val for later use
            best_val[nowW] = bestValThisRun;
        }

        System.out.println("best_val: ");
        printArray(best_val);

        System.out.println("parent: ");
        printArray(parent);

        // print the dag
        int nowWeightIndex = max_w;
        while(true) {
            int nowItemIndex = itemPicked[nowWeightIndex];
            System.out.printf("(%d) - picked item# %d w:%d v:%d%n", nowWeightIndex, nowItemIndex, w[nowItemIndex], v[nowItemIndex]);
            nowWeightIndex = parent[nowWeightIndex];
            if (nowWeightIndex == 0) break;
        }

        value = best_val[max_w];
        return value;
    }

    private static void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(" ");
            System.out.print(array[i]);
        }
        System.out.println();
    }
}