Dynamic Programming • Unbounded Knapsack

Unbounded Knapsack

Given weights and values of items, put them in a knapsack of capacity W to get the maximum value. You are allowed to use an unlimited number of instances of an item.

Try Interactive Simulator

Overview

Unlike 0/1 Knapsack where you can only use an item once, Unbounded Knapsack allows you to pick an item as many times as you want as long as it fits.

1D DP Array

We use a 1D array `dp` of size `W + 1`. `dp[w]` stores the maximum value achievable with a knapsack capacity of exactly `w`.

The Transition

For a capacity `w`, we try adding every item `i`. If `wt[i] <= w`, the new value is `dp[w - wt[i]] + val[i]`. We take the max over all items.

Forward Traversal

Unlike 1D 0/1 Knapsack which iterates the capacity backwards, we iterate forwards. This is because we *want* to be able to reuse the same item multiple times (e.g., to compute `dp[w]`, we can use the already-updated `dp[w - wt[i]]`).

Item 0Wt:2Val:1

Item 1Wt:3Val:2

Item 2Wt:4Val:5

DP Array (Max Value at Capacity W)

0

1

0

2

0

3

0

4

0

5

0

6

0

7

0

8

0

Code Tracker

:::

1let dp = new Array(W + 1).fill(0);

2// Note: loops can be swapped in Unbounded Knapsack

3for (let w = 0; w <= W; w++) {

4 for (let i = 0; i < wt.length; i++) {

5 if (wt[i] <= w) {

6 dp[w] = Math.max(dp[w], dp[w - wt[i]] + val[i]);

7 }

8 }

9}

10return dp[W];