IntermediateDynamic Programming

Knapsack

0/1, unbounded, bounded, and multi-dimensional knapsack patterns

Time: O(nW)
Space: O(W)
Pattern Overview

Core Idea

Pick or skip items with weight/cost constraints; iterate capacity in proper order to avoid reuse bugs.

When to Use

Use for resource allocation with capacity constraints and combinatorial choices.

General Recognition Cues
General indicators that this pattern might be applicable
  • Capacity limit
  • Pick/skip
  • Values/weights
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

0/1 Knapsack

Each item at most once

When to Use This Variant
  • Binary choice
Use Case
Subset value max
Advantages
  • O(nW)
  • 1D optimize
Implementation
def knapsack_01(weights, values, W):
    dp=[0]*(W+1)
    for w,v in zip(weights, values):
        for c in range(W, w-1, -1):
            dp[c]=max(dp[c], dp[c-w]+v)
    return dp[W]
2

Unbounded

Unlimited items

When to Use This Variant
  • Complete knapsack
Use Case
Coin change min ways
Advantages
  • Forward iteration of W
Implementation
def unbounded_knapsack(weights, values, W):
    dp=[0]*(W+1)
    for i,(w,v) in enumerate(zip(weights, values)):
        for c in range(w, W+1):
            dp[c]=max(dp[c], dp[c-w]+v)
    return dp[W]
3

Bounded/Multi

Limited counts or multi-constraints

When to Use This Variant
  • Counts or extra dims
Use Case
Multi-resource
Advantages
  • General but heavier
Implementation
# Bounded counts via binary splitting
def bounded_knapsack(weights, values, counts, W):
    items=[]
    for w,v,c in zip(weights,values,counts):
        k=1
        while c>0:
            take=min(k,c); items.append((w*take, v*take)); c-=take; k<<=1
    dp=[0]*(W+1)
    for w,v in items:
        for c in range(W, w-1, -1):
            dp[c]=max(dp[c], dp[c-w]+v)
    return dp[W]
Common Pitfalls
Watch out for these common mistakes
  • Iterating capacity wrong direction
  • Double counting items
  • Space blow-up
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(nW)

n items by capacity W.

Space Complexity
O(W)

1D rolling array often works.

Ready to test your knowledge?

Test your pattern recognition with interactive questions