0/1 knapsack
Choose items with given weights and values to maximize total value without exceeding a capacity. Each item may be used at most once.
Course progress
Problem 50 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
weights = [2, 3, 4, 5]; values = [3, 4, 5, 8]; capacity = 5
Expected output
8
What is happening?
Taking the weight-5 item uses the full capacity and earns value 8. The best alternative, weights 2 and 3, earns only 7.
Solution strategy
Build the right mental model
Store the best value for every capacity. Process capacities downward for each item so that an item cannot contribute more than once in the same iteration.
Core concepts
dynamic programming · optimization
Complexity
Time O(items x capacity), space O(capacity).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for zero-one-knapsack
using System;
class Program
{
static int MaximumValue(int[] weights, int[] values, int capacity)
{
if (weights.Length != values.Length)
throw new ArgumentException("Weights and values must have equal lengths.");
int[] best = new int[capacity + 1];
for (int item = 0; item < weights.Length; item++)
for (int limit = capacity; limit >= weights[item]; limit--)
best[limit] = Math.Max(best[limit], best[limit - weights[item]] + values[item]);
return best[capacity];
}
static void Main()
{
Console.WriteLine(MaximumValue(
new[] { 2, 3, 4, 5 },
new[] { 3, 4, 5, 8 },
5));
}
}Knowledge check
Questions students often ask
What is the main idea behind 0/1 knapsack?
Store the best value for every capacity. Process capacities downward for each item so that an item cannot contribute more than once in the same iteration.
What is the time and space complexity of this solution?
Time O(items x capacity), space O(capacity).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.