The 0-1 Knapsack Problem is a classic optimization problem where you need to determine the maximum value that can be obtained by selecting items with given weights and values, while keeping the total weight within a specified limit (the capacity of the knapsack). Each item can either be included in the knapsack (1) or excluded (0), hence the name “0-1 Knapsack”.
Problem Definition
- You have
n
items, each with a weightweights[i]
and a valuevalues[i]
. - You need to maximize the total value of the items in the knapsack without exceeding the maximum weight
W
.
Dynamic Programming Approach
-
Dynamic Programming Table: Create a 2D array
dp
wheredp[i][w]
represents the maximum value that can be attained with the firsti
items and maximum weightw
. -
Initialization: Initialize the first row and first column of the
dp
table to 0, as the maximum value is 0 when there are no items or the maximum weight is 0. -
Filling the DP Table:
- Loop through each item and for each weight from 1 to
W
. - If the weight of the current item is less than or equal to
w
, you can choose to include it or not. The formula is:dp[i][w] = Math.Max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
- If the weight of the current item exceeds
w
, you cannot include it:dp[i][w] = dp[i - 1][w]
- Loop through each item and for each weight from 1 to
-
Result: The value in
dp[n][W]
will be the maximum value that can be attained.
C# Implementation
Here’s how you can implement the 0-1 Knapsack problem in C#:
using System;
class Program
{
static void Main()
{
int[] values = { 60, 100, 120 };
int[] weights = { 10, 20, 30 };
int capacity = 50;
int maxValue = Knapsack(values, weights, capacity);
Console.WriteLine("Maximum value in Knapsack = " + maxValue);
}
static int Knapsack(int[] values, int[] weights, int capacity)
{
int n = values.Length;
int[,] dp = new int[n + 1, capacity + 1]; // DP table
// Fill the DP table
for (int i = 1; i <= n; i++)
{
for (int w = 1; w <= capacity; w++)
{
if (weights[i - 1] <= w)
{
dp[i, w] = Math.Max(dp[i - 1, w], dp[i - 1, w - weights[i - 1]] + values[i - 1]);
}
else
{
dp[i, w] = dp[i - 1, w];
}
}
}
return dp[n, capacity]; // Return the maximum value
}
}
Explanation of Code
- Input: The program defines arrays
values
andweights
, which represent the values and weights of the items, along with thecapacity
of the knapsack. - Knapsack Function:
- Initializes a 2D array
dp
of size(n + 1) x (capacity + 1)
, wheren
is the number of items.
- Initializes a 2D array
- Filling the DP Table:
- Two nested loops iterate through the items and possible weights.
- If the weight of the current item is less than or equal to
w
, it considers both including and excluding the item, updating thedp
table accordingly. - If the item cannot be included (due to weight), it simply takes the value from the previous row.
- Return Result: The function returns
dp[n, capacity]
, which contains the maximum value achievable with the given items and weight capacity.
Complexity
- Time Complexity: O(n * W), where
n
is the number of items andW
is the maximum capacity of the knapsack. This arises from filling out the DP table. - Space Complexity: O(n * W) for the
dp
table.
Space Optimization
The space complexity can be optimized to O(W) by using a single-dimensional array to keep track of the maximum values. This involves updating the array in reverse order to prevent overwriting values that are still needed for calculations.
Summary
This dynamic programming approach effectively solves the 0-1 Knapsack problem, providing a clear and efficient method to determine the maximum value that can be packed into the knapsack given the constraints.