Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.
In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W.
1 ≤ n ≤ 1001 ≤ weights[i], values[i] ≤ 10001 ≤ W ≤ 1000For each item, you can either include it in the knapsack or exclude it.
220