import java.awt.*;

public class DP_Knapsack_Norepetition_CountWeight_Assignment {

    public static void main(String[] args) {

        int w[] = new int[]{1, 4, 6, 2, 5, 10, 8, 3, 9, 1, 4, 2, 5, 8, 9, 1};
        int v[] = new int[]{ 10, 5, 30, 8, 12, 30, 50, 10, 2, 10, 40, 80, 100, 25, 10, 5 };
        int max_w = 20;

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

//        int w[] = new int[]{11,11,11,2};
//        int v[] = new int[]{30,14,16,9};
//
//        int max_w = 10;


        dp_knapsack_repitition(w, v, max_w);
        System.out.println();
    }

    private static int dp_knapsack_repitition(int[] w, int[] v, int max_w) {
        int best_val[][] = new int[max_w + 1][v.length]; // attention: we intend to allow from 0 ~ 10 (11 numbers instead of 10 numbres)
        int parent_row[][] = new int[max_w + 1][v.length];
        int parent_col[][] = new int[max_w + 1][v.length];
        int iterationCount = 0;

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

        // set the base state -> w = 0
        for (int itemIndex = 0; itemIndex < v.length; itemIndex++) {
            best_val[0][itemIndex] = 0;
            parent_row[0][itemIndex] = -1; // no parent for the base case
            parent_col[0][itemIndex] = -1; // no parent for the base case
        }

        // set the base state -> v = 0 (no item is picked)
        for (int wIndex = 0; wIndex < max_w + 1; wIndex++) {
            best_val[wIndex][0] = 0;
            parent_row[wIndex][0] = -1; // no parent for the base case
            parent_col[wIndex][0] = -1; // no parent for the base case
        }


        System.out.println("\r\nbase 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

                // increment iteraiton count
                iterationCount++;

                // 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]);
                    parent_row[nowW][itemIndex] = nowW - w[itemIndex]; // attention: if picked, the affordable weight will go down
                    parent_col[nowW][itemIndex] = itemIndex;
                }else if (w[itemIndex] <= nowW && itemIndex != 0) { // if this is not the first item, then we decide whether to pick this one or not

                    // get the better one
                    int noPick = best_val[nowW][itemIndex - 1];
                    int pick = v[itemIndex] + best_val[nowW - w[itemIndex]][itemIndex - 1];

                    if (noPick > pick){
                        parent_row[nowW][itemIndex] = nowW;
                        parent_col[nowW][itemIndex] = itemIndex - 1;
                    } else {
                        parent_row[nowW][itemIndex] = nowW - w[itemIndex]; // attention: if picked, the affordable weight will go down
                        parent_col[nowW][itemIndex] = itemIndex - 1;
                    }

                    tmpVal = Math.max(noPick, pick); // 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 previous item for this weight limit
                    parent_row[nowW][itemIndex] = nowW;
                    parent_col[nowW][itemIndex] = itemIndex - 1;
                }

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

        } // end of outer for


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

//        System.out.println("final row: ");
//        print2DArray(parent_row);
//
//        System.out.println("final col: ");
//        print2DArray(parent_col);

        // print parent
        System.out.println("\nThe final route: ");
        int currentRow = max_w;
        int currentCol = v.length-1;
        while(true){

            System.out.printf("(%d,%d)%n" , currentRow, currentCol);

            int newParentRow = parent_row[currentRow][currentCol];
            int newParentCol = parent_col[currentRow][currentCol];
            if (newParentRow < 0 || newParentCol < 0) break;

            currentRow = newParentRow;
            currentCol = newParentCol;

        }

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

        System.out.println("\nWeight: " + weight);
        System.out.println("Value: " + value);
        System.out.println("the number of iterations : " + iterationCount);

        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();
        }
    }
}