0/1, unbounded, bounded, and multi-dimensional knapsack patterns
Pick or skip items with weight/cost constraints; iterate capacity in proper order to avoid reuse bugs.
Use for resource allocation with capacity constraints and combinatorial choices.
0/1 knapsack iterates capacity in reverse; unbounded iterates forward; extend with counts or extra dimensions when bounded/multi-constraint.
# Digit DP Template (No consecutive ones up to N)
from functools import lru_cache
def count_no_consec_ones(n):
s=bin(n)[2:]
@lru_cache(None)
def dp(i, tight, prev1):
if i==len(s): return 1
up = int(s[i]) if tight else 1
total=0
for d in range(up+1):
if prev1 and d==1: continue
total+=dp(i+1, tight and d==up, d==1)
return total
return dp(0, True, False)Each item at most once
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]Unlimited items
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]Limited counts or multi-constraints
# 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]n items by capacity W.
1D rolling array often works.