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.
Inputs:
- values[]: Array representing the values of the items.
- weights[]: Array representing the weights of the items.
- W: Total capacity of the knapsack.
- n: Number of items.
Output:
- Maximum value that can be achieved with items whose combined weight is less than or equal to W.
Example
int[] values = {60, 100, 120};
int[] weights = {10, 20, 30};
int W = 50;
int n=3;
int result = Knapsack(weights, values, W);
Outputs: 220
One practical application of this problem is the problem of loading items in a container of limited carrying capacity in such a way that it maximizes the value by carrying the minimum weight. Items with great value but minimum weight will be selected.
Solution: We can use dynamic programming to solve this problem. Let's define a 2D array dp[i][w] where i is the item index and w is the weight. dp[i][w] will represent the maximum value we can achieve using the first i items and a knapsack of weight w.
Here's the C# code to solve the Knapsack problem:
public int KnapsackRecursive(int[] values, int[] weights, int n, int W) {
// Base condition
if (n == 0 || W == 0) return 0;
// If the weight of the nth item is more than the capacity W,
// then this item cannot be included in the optimal solution
if (weights[n - 1] > W) {
return KnapsackRecursive(values, weights, n - 1, W);
}
// Return the maximum of two cases:
// (1) nth item included
// (2) nth item not included
return Math.Max(
values[n - 1] + KnapsackRecursive(values, weights, n - 1, W - weights[n - 1]),
KnapsackRecursive(values, weights, n - 1, W)
);
}
This solution is not efficient for larger values
we need to store previously computed values in a dictionary or array. This technique is called memoization.
public int Knapsack(int[] values, int[] weights, int W) {
int totalItems = weights.Length;
int?[,] memo = new int?[totalItems, W + 1];
return KnapsackRecursive(values, weights, W, totalItems - 1, memo);
}
private int KnapsackRecursive(int[] values, int[] weights, int W, int n, int?[,] memo) {
// Base cases
if (n < 0 || W <= 0) {
return 0;
}
// If result is already computed, return it
if (memo[n, W].HasValue) {
return memo[n, W].Value;
}
// Exclude the current item
int exclude = KnapsackRecursive(values, weights, W, n - 1, memo);
// Include the current item (if possible)
int include = (weights[n] <= W)
? values[n] + KnapsackRecursive(values, weights, W - weights[n], n - 1, memo)
: 0;
// Store the result in memo table and return the maximum of include and exclude
memo[n, W] = Math.Max(include, exclude);
return memo[n, W].Value;
}