☕ DSA Java Articles

Topics › Dynamic Programming › DP on Subsequences

Unbounded knapsack

Hard TUF ID 325 A2Z

Java source ↗ Edit this article ↗

Problem

You are given n item types. Item i has weight wt[i] and value val[i], and you have an unlimited supply of every item. A knapsack can carry a total weight of at most cap. Choose how many copies of each item to pack (zero is allowed) so that the total weight does not exceed cap and the total value is as large as possible. Return that value.

Weights are positive integers and values are non-negative integers. Typical limits put n and cap around 1000 with weights and values of at most a few hundred, so n · cap is about a million and every answer fits comfortably in an int. GeeksforGeeks lists the same task as “Knapsack with Duplicate Items”.

Example 1

wt = [2, 4, 6], val = [5, 11, 13], cap = 10
answer = 27          // two copies of weight 4 (22) plus one of weight 2 (5), total weight 10

Example 2

wt = [5, 6], val = [10, 13], cap = 10
answer = 20          // two copies of weight 5; the "better ratio" item 6 fits only once (13)

Example 3

wt = [3, 4], val = [5, 6], cap = 2
answer = 0           // nothing fits, so the knapsack stays empty

Why greedy by value per weight fails

The tempting idea is to pack the item with the best value-to-weight ratio as many times as possible, then fill the rest with the next best, and so on. That is exactly right for Fractional Knapsack, where items can be cut, because no capacity is ever wasted. Here items are indivisible, and the leftover space matters. In Example 2 the weight-6 item has ratio 13 / 6 ≈ 2.17, better than 10 / 5 = 2, but taking it leaves 4 units of capacity that nothing fits into, for a total of 13. Two copies of the “worse” item fill the knapsack exactly and give 20. We need to consider every count of every item, which is what the DP does efficiently.

How unlimited copies change the recursion

Process the items from the last index down to 0. The state is (i, w): items 0..i may still be used, and w capacity is left. From any state there are two choices:

Staying at i is the only difference from the 0/1 knapsack, where taking an item moves to i - 1. Every choice of “how many copies of item i” is a run of take-steps followed by one not-take step, so the recursion still explores every legal packing. It terminates because each step either lowers i or lowers w by at least 1 (weights are positive).

The base case is i = 0: only item 0 is left. Since values are non-negative, extra copies never hurt, so the best is to pack as many as fit, w / wt[0] copies (integer division), worth (w / wt[0]) · val[0]. That single formula also covers w < wt[0] (zero copies) and w = 0.

f(0, w) = (w / wt[0]) * val[0]
f(i, w) = max( f(i - 1, w),  val[i] + f(i, w - wt[i])  if wt[i] ≤ w )
answer  = f(n - 1, cap)

Unlike coin change, the knapsack need not be filled exactly; the capacity is an upper bound. So there is no “impossible” state and no sentinel like INF: every state has a valid answer of at least 0.

Approach 1: Recursion

Intuition. Code the recurrence directly. Each call settles one question: take another copy of item i, or never use item i again. It is correct because it tries every packing, but it recomputes the same (i, w) many times through different paths.

Algorithm.

  1. If i == 0, return (w / wt[0]) · val[0].
  2. notTake = f(i - 1, w).
  3. take = val[i] + f(i, w - wt[i]) if wt[i] ≤ w, else 0.
  4. Return max(notTake, take).
static int recursive(int[] wt, int[] val, int cap) {
    return solve(wt.length - 1, cap, wt, val);
}

static int solve(int i, int w, int[] wt, int[] val) {
    if (i == 0) return (w / wt[0]) * val[0];                     // only item 0 left: take as many as fit
    int notTake = solve(i - 1, w, wt, val);
    int take = wt[i] <= w ? val[i] + solve(i, w - wt[i], wt, val) : 0;   // stay on i: unlimited copies
    return Math.max(notTake, take);
}

Complexity. Time is exponential. Every call branches twice and the depth can reach about n + cap / min(wt), so O(2^(n + cap)) is a safe bound. Space is the recursion depth, O(n + cap).

Using 0 as the “take” value when the item does not fit is safe only because values are non-negative: the not-take branch is always at least 0, so a 0 never wins wrongly.

Approach 2: Memoization

Intuition. The best value from (i, w) does not depend on which path led there, and there are only n · (cap + 1) distinct states. Cache each result the first time it is computed. All real answers are ≥ 0, so -1 safely means “not computed yet”.

Algorithm.

  1. Allocate dp[n][cap + 1] and fill it with -1.
  2. Run the same recursion; return dp[i][w] if it is known, otherwise compute it and store it.
static int memoization(int[] wt, int[] val, int cap) {
    int[][] dp = new int[wt.length][cap + 1];
    for (int[] row : dp) Arrays.fill(row, -1);                       // values are >= 0, so -1 = unknown
    return memo(wt.length - 1, cap, wt, val, dp);
}

static int memo(int i, int w, int[] wt, int[] val, int[][] dp) {
    if (i == 0) return (w / wt[0]) * val[0];
    if (dp[i][w] != -1) return dp[i][w];
    int notTake = memo(i - 1, w, wt, val, dp);
    int take = wt[i] <= w ? val[i] + memo(i, w - wt[i], wt, val, dp) : 0;
    return dp[i][w] = Math.max(notTake, take);
}

Complexity. Time O(n · cap): each state is solved once with constant work. Space O(n · cap) for the table plus O(n + cap) stack. A weight-1 item and cap = 10^4 would mean ten thousand nested calls, which can overflow Java’s default stack; tabulation avoids that.

Approach 3: Tabulation

Intuition. Look at which cells the recurrence reads. dp[i][w] needs dp[i - 1][w] (the row above) and dp[i][w - wt[i]] (the same row, further left). So fill rows from i = 0 upward and each row from w = 0 to cap; both dependencies are then final when needed. Row 0 is the base case.

This same-row read is what “unlimited supply” looks like in a table. In the 0/1 knapsack, “take” reads dp[i - 1][w - wt[i]] from the row above, which is how it forbids a second copy. Here dp[i][w - wt[i]] may itself already include copies of item i, so taking item i once more on top of it is allowed.

Algorithm.

  1. For every w, set dp[0][w] = (w / wt[0]) · val[0].
  2. For i = 1..n-1 and w = 0..cap: dp[i][w] = max(dp[i - 1][w], val[i] + dp[i][w - wt[i]]), the second term only when wt[i] ≤ w.
  3. Return dp[n - 1][cap].
static int tabulation(int[] wt, int[] val, int cap) {
    int n = wt.length;
    int[][] dp = new int[n][cap + 1];
    for (int w = 0; w <= cap; w++) dp[0][w] = (w / wt[0]) * val[0];
    for (int i = 1; i < n; i++) {
        for (int w = 0; w <= cap; w++) {
            int notTake = dp[i - 1][w];
            int take = wt[i] <= w ? val[i] + dp[i][w - wt[i]] : 0;     // same row: item i may be taken again
            dp[i][w] = Math.max(notTake, take);
        }
    }
    return dp[n - 1][cap];
}

Complexity. Time O(n · cap), space O(n · cap).

Approach 4: Space optimized

Intuition. Each row only needs the row above and itself, so one array best is enough. Before item i is processed, best[w] holds the row above. Sweeping w from left to right replaces each entry with the current row’s value, and when best[w] is updated, best[w - wt[i]] to its left already belongs to the current row, so it may already contain copies of item i. That is precisely the same-row read from Approach 3.

The direction is the whole trick. The 0/1 knapsack sweeps right to left so that best[w - wt[i]] is still the old row; running this loop right to left would silently turn the code into the 0/1 version.

We can also start from a simpler base: an all-zero array means “with no items yet, every capacity is worth 0”. Processing item 0 left to right then produces (w / wt[0]) · val[0] on its own, because each step adds one more copy whenever it fits, so the special base row disappears. Starting the inner loop at w = wt[i] skips capacities where item i cannot fit; those entries keep their row-above value, which is what the not-take branch would give.

Algorithm.

  1. best = new int[cap + 1], all zeros.
  2. For each item i, for w from wt[i] up to cap: best[w] = max(best[w], val[i] + best[w - wt[i]]).
  3. Return best[cap].
static int spaceOptimized(int[] wt, int[] val, int cap) {
    int[] best = new int[cap + 1];                                   // with no items, every capacity is worth 0
    for (int i = 0; i < wt.length; i++) {
        for (int w = wt[i]; w <= cap; w++) {                         // left to right: best[w - wt[i]] may hold item i
            best[w] = Math.max(best[w], val[i] + best[w - wt[i]]);
        }
    }
    return best[cap];
}

Dry run on Example 1 (wt = [2, 4, 6], val = [5, 11, 13], cap = 10), showing best[0..10] after each item:

after item best[0..10]
(2, 5) 0 0 5 5 10 10 15 15 20 20 25
(4, 11) 0 0 5 5 11 11 16 16 22 22 27
(6, 13) 0 0 5 5 11 11 16 16 22 22 27

After item (4, 11), best[10] = 11 + best[6] = 11 + 16 = 27, and best[6] = 11 + best[2] was itself updated earlier in the same sweep, so it already used one copy of weight 4. That chain is two copies of weight 4 plus one of weight 2. Item (6, 13) improves nothing: the best it offers at capacity 10 is 13 + best[4] = 24.

Complexity. Time O(n · cap), space O(cap).

For maximisation the loop order can also be swapped: for each capacity w, take best[w] = max over items i with wt[i] ≤ w of val[i] + best[w - wt[i]]. Both orders give the same answer here, because a maximum does not care in which order the items of a packing were chosen. That freedom does not exist when counting, as Coin Change 2 (DP - 22) explains: there, swapping the loops counts ordered sequences instead of combinations.

Edge cases and pitfalls