| 2 | |
| 3 | class knapsack { |
| 4 | int knap(int[] wt, int[] val, int W, int n) { |
| 5 | int[][] M = new int[n + 1][W + 1]; |
| 6 | for (int i = 0; i <= n; i++) { |
| 7 | for (int w = 0; w <= W; w++) { |
| 8 | if (w == 0 || i == 0) |
| 9 | M[i][w] = 0; |
| 10 | else if (wt[i - 1] > w) |
| 11 | M[i][w] = M[i - 1][w]; |
| 12 | else |
| 13 | M[i][w] = Math.max(M[i - 1][w], val[i - 1] + M[i - 1][w - wt[i - 1]]); |
| 14 | } |
| 15 | } |
| 16 | int i = n, k = W; |
| 17 | while (i > 0 && k > 0) { |
| 18 | if (M[i][k] != M[i - 1][k]) { |
| 19 | System.out.println(i); |
| 20 | i = i - 1; |
| 21 | k = k - wt[i]; |
| 22 | } else |
| 23 | i = i - 1; |
| 24 | } |
| 25 | return M[n][W]; |
| 26 | } |
| 27 | |
| 28 | public static void main(String[] args) { |
| 29 | int[] val = new int[] { 10, 4, 9, 11 }; |