✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-174

0/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

Items

NameWeightValue

A

2

3

B

3

4

C

4

5

Capacity

5

Selected Items

  • A

  • B

Total Weight

5

Maximum Value

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.

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.

Key Concepts

  • Include-or-exclude decisions

  • State transition

  • Optimal substructure

  • Overlapping subproblems

  • Capacity constraint

  • Descending capacity iteration

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.

Applications

  • Budget allocation.

  • Cargo and loading optimization.

  • Resource selection.

  • Investment selection under constraints.

  • Project planning.

Related Topics

  • Unbounded Knapsack Problem

  • Subset Sum Problem

  • Dynamic Programming

  • Combinatorial Optimization

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