Unbounded Knapsack

Medium20–25 min

Topics

Dynamic ProgrammingArray

Companies

AmazonFlipkartPaytm

Given a set of items, each with a weight and a value, and a bag with a maximum weight capacity, choose items — each one reusable as many times as it fits — that maximize the total value packed into the bag without exceeding its capacity. Unlike the standard knapsack, any item can be placed in more than once. Every item still faces a decision at every point, but now that decision is "move on for good" versus "use this item again": moving on keeps the current capacity but permanently rules the item out, while using it again banks its value, spends its weight, and leaves it just as available as before for the leftover capacity. Because an item can contribute any number of times, tracking the best value reachable at every capacity — and letting each item's own update reuse results that already include that same item — captures unlimited reuse without ever explicitly counting how many copies were taken.

Test Case 1:

Input:weights = [3, 4, 5], values = [4, 5, 6], capacity = 6

Output:8

Explanation:Taking item 0 (weight 3, value 4) twice fills the bag exactly (weight 6) for a value of 8 — better than any single-item or mixed combination.

Test Case 2:

Input:weights = [2], values = [3], capacity = 7

Output:9

Explanation:Taking item 0 three times uses weight 6 out of 7 for a value of 9 — the leftover 1 unit of capacity can't fit a fourth copy.

Test Case 3:

Input:weights = [5], values = [10], capacity = 3

Output:0

Explanation:The only item weighs more than the capacity, so nothing can be taken, even once.

Constraints

◆1 ≤ weights.length = values.length ≤ 20
◆1 ≤ weights[i], values[i] ≤ 100
◆0 ≤ capacity ≤ 1000

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

This is the same weight-and-value decision as the standard knapsack, except an item that's placed in the bag doesn't get used up — it can be placed in again as many times as it still fits. Every item is either skipped for good (move permanently to the next item, capacity unchanged) or taken once more (bank its value, use up its weight, and consider that same item again from the current capacity). Both choices are tried wherever an item still fits, and the larger of the two resulting totals is kept. Running out of items or capacity ends a path with whatever value has already been collected.

TimeO(2^capacity)

SpaceO(capacity)

Java

Try it out

class Solution {
    private int[] weights;
    private int[] values;

    public int unboundedKnapsack(int[] weights, int[] values, int capacity) {
        this.weights = weights;
        this.values = values;
        return solve(0, capacity);
    }

    private int solve(int i, int capacity) {
        if (i == weights.length || capacity == 0) return 0;
        if (weights[i] > capacity) return solve(i + 1, capacity);
        int skip = solve(i + 1, capacity);
        int take = values[i] + solve(i, capacity - weights[i]);
        return Math.max(skip, take);
    }
}

Optimal — Bottom-Up 1D DP

Optimal

Track, for every capacity from 0 up to the bag's full capacity, the best total value achievable using the items considered so far. The key difference from the one-copy-per-item version is the direction the inner sweep runs: going from each item's own weight up to the full capacity — rather than backward — means that when dp[w - weight] is looked up, it may already include this same item, which is exactly what allows it to be counted more than once. Every item can still be skipped (the value at that capacity stays whatever it already was) or taken (its value plus the best value at the capacity left over, possibly including itself again), and the larger of the two is kept. The entry at the full capacity holds the answer once every item has been swept through.

TimeO(n × capacity)