0/1 Knapsack Problem?

int Knapsack(int[] weights, int[] values, int W)

int n = weights.Length;

int[,] dp = new int[n + 1, W + 1];

for (int i = 1; i <= n; i++)

for (int w = 1; w <= W; w++)

if (weights[i - 1] <= w)

dp[i, w] = Math.Max(dp[i - 1, w], values[i - 1] +

dp[i - 1, w - weights[i - 1]]);

else

dp[i, w] = dp[i - 1, w];

return dp[n, W];

Explanation:

Build table where dp[i,w] = max value using first i items and capacity w.

Follow on: