#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/knapsack/unbounded-knapsack-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/knapsack/unbounded-knapsack-implementation

Repovive

Unbounded Knapsack - Implementation - Knapsack | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

Unbounded Knapsack - Implementation

The code

dp[0] = 0
for w from 1 to W:
    dp[w] = 0
for i from 1 to n:
    if w[i] <= w:
        dp[w] = max(dp[w], dp[w-w[i]] + v[i])
return dp[W]

Time: $O(n \times W)$ . Space: $O(W)$ .

The inner loop tries adding each item to capacity $w$ . Since items are unlimited, you use dp[w-w[i]] from the same row. This lets you pick the same item multiple times.

Compare this to 0/1 knapsack where you use dp[i-1][w-w[i]] to prevent reuse. The single-row approach naturally allows repetition.