public int knapsackdp(int[]w, int[]v, int W) {
        int N = w.length;
        int[][] path = new int[W+1][N];
        int[] sol = new int[W+1];
        for(int i = 1; i <= W; i++) {
            for(int k = 0; k < N; k++) {
                if(i - w[k] >= 0 && v[k] + sol[i-w[k]] > sol[i]) {
                    sol[i] = v[k] + sol[i-w[k]];
                    path[i] = Arrays.copyOf(path[i-w[k]], N);
                    path[i][k]++;
                }
            }
        }
        System.out.println(Arrays.toString(path[W]));
        return sol[W];
    }