Unbounded Knapsack (Repetition of items allowed)

Problem Statement

Given a knapsack of capacity W and n items with given weights and values, fill the knapsack to maximize total value. Unlike the 0/1 knapsack, here you can use each item any number of times (unlimited supply).

Example:

• Input: W = 8, weights = [1, 3, 4, 5], values = [10, 40, 50, 70]
• Output: 110 (Take two items of weight 3 (value 40 each) + one item of weight 1 (value 10) + one more of weight 1 (value 10) → wait, better: weight 3+5=8, value 40+70=110)

Noob-Friendly Explanation

Imagine you have a backpack that can carry W kilograms. You're at a store with different items, each with a weight and a value. Unlike a normal store where each item is one-of-a-kind, this store has unlimited copies of everything! You can pick the same item as many times as you want, as long as the total weight fits in your backpack. What's the most valuable collection you can carry?

Approach 1: Brute Force

Intuition

For each item, we have a choice: include it (and we can include it again) or move to the next item. Try all combinations recursively.

Algorithm

1. For each item, try including it 0, 1, 2, ... times (as long as weight allows).
2. Recursively compute the maximum value for the remaining capacity.
3. Return the maximum value found.

class Solution {
    public static int unboundedKnapsackBrute(int[] weights, int[] values, int n, int W) {
        if (W == 0 || n == 0) return 0;

        int exclude = unboundedKnapsackBrute(weights, values, n - 1, W);

        int include = 0;
        if (weights[n - 1] <= W) {
            // Note: n stays the same because we can reuse the item
            include = values[n - 1] +
                      unboundedKnapsackBrute(weights, values, n, W - weights[n - 1]);
        }

        return Math.max(include, exclude);
    }

    public static void main(String[] args) {
        int[] weights = {1, 3, 4, 5};
        int[] values = {10, 40, 50, 70};
        int W = 8;
        System.out.println(unboundedKnapsackBrute(weights, values, weights.length, W));
        // Output: 110
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - exponential branching (actually worse because of repetition, but bounded by capacity)
• Space Complexity: O(W) - recursion stack depth limited by capacity

Approach 2: Optimal

Intuition

Use a 1D DP array where dp[w] represents the maximum value achievable with capacity w. For each capacity, try all items and pick the best one.

Algorithm

1. Create a dp array of size W + 1, initialized to 0.
2. For each capacity w from 1 to W, for each item i, if the item fits (weights[i] <= w), update: dp[w] = max(dp[w], dp[w - weights[i]] + values[i]).
3. Return dp[W].

class Solution {
    public static int unboundedKnapsack(int[] weights, int[] values, int W) {
        int n = weights.length;
        int[] dp = new int[W + 1];

        for (int w = 1; w <= W; w++) {
            for (int i = 0; i < n; i++) {
                if (weights[i] <= w) {
                    dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
                }
            }
        }

        return dp[W];
    }

    public static void main(String[] args) {
        int[] weights = {1, 3, 4, 5};
        int[] values = {10, 40, 50, 70};
        int W = 8;
        System.out.println(unboundedKnapsack(weights, values, W)); // Output: 110
    }
}

Complexity Analysis

• Time Complexity: O(n * W) - two nested loops
• Space Complexity: O(W) - the 1D dp array