concept · INFO-CS-ADS-1740/1 Knapsack Problem
Learn how dynamic programming selects items with given weights and values to maximize total value without exceeding a fixed capacity, while allowing each item to be selected at most once.
Explanation
Overview
The 0/1 Knapsack Problem is an optimization problem in which a collection of items has individual weights and values. A knapsack has a maximum weight capacity, and each item must either be selected completely or not selected at all.
Key concepts
Include-or-exclude decisions; State transition; Optimal substructure; Overlapping subproblems; Capacity constraint; Descending capacity iteration
Variables
i: The number of items considered.; w: The current available knapsack capacity.; weight[i]: The weight of item i.; value[i]: The value of item i.; dp[i][w]: The maximum value achievable using the first i items with capacity w.
Complexity
twoDimensionalTabulation: O(nW) time and O(nW) space.; spaceOptimized: O(nW) time and O(W) space.; variables: n is the number of items and W is the integer capacity.
Example
items: name: A; weight: 2; value: 3; name: B; weight: 3; value: 4; capacity: 5; selectedItems: A; B; totalWeight: 5; maximumValue: 7; explanation: Selecting A and B gives a total value of 7 without exceeding the capacity. Each item can be used no more than once.
Pseudocode
function knapsack(weights, values, n, capacity):
dp = array of size capacity + 1 filled with 0
for i = 0 to n - 1:
for w = capacity down to weights[i]:
dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
return dp[capacity]
Applications
Budget allocation.; Cargo and loading optimization.; Resource selection.; Investment selection under constraints.; Project planning.
Variables
I
The number of items considered.
W
The current available knapsack capacity.
Weight[i]
The weight of item i.
Value[i]
The value of item i.
Dp[i][w]
The maximum value achievable using the first i items with capacity w.
Example or application
Explanation
Selecting A and B gives a total value of 7 without exceeding the capacity. Each item can be used no more than once.
Definition
The 0/1 Knapsack Problem is an optimization problem in which a collection of items has individual weights and values. A knapsack has a maximum weight capacity, and each item must either be selected completely or not selected at all.
Mathematical Representation
dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]]) when weight[i] <= w; otherwise dp[i][w] = dp[i-1][w].
Approaches
Recursive
For each item, consider two possibilities: include it if it fits, or exclude it.
Memoization
Stores results for previously solved combinations of item index and remaining capacity.
Tabulation
Builds a two-dimensional table using the previous item row to calculate each new state.
Space Optimized
Uses a one-dimensional array and processes capacities in descending order to prevent selecting the same item multiple times.
Pseudocode
function knapsack(weights, values, n, capacity):
dp = array of size capacity + 1 filled with 0
for i = 0 to n - 1:
for w = capacity down to weights[i]:
dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
return dp[capacity]
Complexity
Two Dimensional Tabulation
O(nW) time and O(nW) space.
Space Optimized
O(nW) time and O(W) space.
Variables
n is the number of items and W is the integer capacity.
Advantages
Finds an optimal selection under the given capacity.
Avoids repeatedly solving identical subproblems.
Supports reconstruction of selected items when decision information is retained.
Provides a foundation for many resource-allocation problems.
Limitations
The O(nW) algorithm is pseudo-polynomial, not polynomial in the number of bits used to represent W.
A large capacity can require substantial time and memory.
The standard 0/1 model assumes items are indivisible and cannot be reused.
Practice Question
An item weighs 3 units and has value 6. Can it be selected twice in the standard 0/1 Knapsack Problem?
Practice Answer
No. Each item can be selected at most once.
Learning Objectives
Explain the central idea and purpose of 0/1 knapsack problem.
Identify the assumptions, inputs, and conditions relevant to 0/1 knapsack problem.
Evaluate an application of 0/1 knapsack problem for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Dynamic Programming Applications
Suggest a correction or source · More in Algorithms & Data Structures