Unbounded Knapsack Problem in DSA Java

Mental Model

We want to fill a bag with items to get the most value, and we can use each item as many times as we want.

Analogy: Imagine you have a backpack and unlimited candies of different sizes and tastiness. You want to fill your backpack to enjoy the most tastiness, and you can pick any candy multiple times.

Capacity: 5
Items: [weight: 1, value: 10], [weight: 3, value: 40], [weight: 4, value: 50]
Backpack: [] -> [] -> [] -> [] -> [] -> null

Dry Run Walkthrough

Input: capacity = 5, items = [(weight=1, value=10), (weight=3, value=40), (weight=4, value=50)]

Goal: Find the maximum value we can get by filling the backpack of capacity 5 using unlimited items.

Step 1: Start with capacity 0, max value is 0 because no space

dp[0] = 0

Why: Base case: no capacity means no items can be taken

Step 2: For capacity 1, try each item: only item with weight 1 fits, value 10

dp[1] = 10

Why: We can take item 1 once to fill capacity 1

Step 3: For capacity 2, try items: item 1 twice (10+10=20), others don't fit

dp[2] = 20

Why: Taking item 1 twice gives max value for capacity 2

Step 4: For capacity 3, try items: item 3 fits once (value 40), or item 1 thrice (30), max is 40

dp[3] = 40

Why: Item 3 alone gives better value than three item 1s

Step 5: For capacity 4, try items: item 4 once (50), item 3 + item 1 (40+10=50), item 1 four times (40), max is 50

dp[4] = 50

Why: Taking item 4 once or item 3 plus item 1 gives max value

Step 6: For capacity 5, try items: item 1 + dp[4] (10+50=60), item 3 + dp[2] (40+20=60), item 4 + dp[1] (50+10=60), max is 60

dp[5] = 60

Why: Combining items in different ways to fill capacity 5 maximizes value

Result:

dp array: [0, 10, 20, 40, 50, 60]
Maximum value for capacity 5 is 60

Annotated Code

DSA Java

public class UnboundedKnapsack {

    static int unboundedKnapsack(int capacity, int[] weights, int[] values) {
        int[] dp = new int[capacity + 1];
        for (int c = 1; c <= capacity; c++) {
            for (int i = 0; i < weights.length; i++) {
                if (weights[i] <= c) {
                    dp[c] = Math.max(dp[c], values[i] + dp[c - weights[i]]);
                }
            }
        }
        return dp[capacity];
    }

    public static void main(String[] args) {
        int capacity = 5;
        int[] weights = {1, 3, 4};
        int[] values = {10, 40, 50};
        int maxValue = unboundedKnapsack(capacity, weights, values);
        System.out.println("Maximum value for capacity " + capacity + " is " + maxValue);
    }
}

for (int c = 1; c <= capacity; c++) {

iterate over all capacities from 1 to max capacity

for (int i = 0; i < weights.length; i++) {

try each item for current capacity

if (weights[i] <= c) {

check if item fits in current capacity

dp[c] = Math.max(dp[c], values[i] + dp[c - weights[i]]);

update max value by including current item and remaining capacity

Output

Maximum value for capacity 5 is 60

Complexity Analysis

Time: O(n * capacity) because we check each item for every capacity from 1 to capacity

Space: O(capacity) because we use a dp array of size capacity+1 to store max values

vs Alternative: Compared to recursive solutions without memoization which can be exponential, this dynamic programming approach is efficient and avoids repeated calculations

Edge Cases

capacity = 0

Returns 0 because no items can be taken

DSA Java

for (int c = 1; c <= capacity; c++) {

items array empty

Returns 0 because no items to choose from

DSA Java

for (int i = 0; i < weights.length; i++) {

items with weight greater than capacity

Those items are skipped because they don't fit

DSA Java

if (weights[i] <= c) {

When to Use This Pattern

When you can use unlimited copies of items to fill a capacity and want to maximize value, reach for the Unbounded Knapsack pattern because it allows repeated item use efficiently.

Common Mistakes

Mistake: Using 0/1 Knapsack logic which disallows repeated items
Fix: Allow repeated use by considering dp[c - weights[i]] in the update step

Mistake: Not initializing dp array properly or starting capacity loop from 0
Fix: Start capacity loop from 1 and initialize dp[0] = 0 as base case

Summary

Finds the maximum value achievable with unlimited copies of given items within a capacity.

Use when items can be chosen multiple times and you want to maximize total value under capacity constraints.

The key is to build up solutions for all capacities by reusing previous results and allowing repeated items.

Practice

1. What is the main difference between the Unbounded Knapsack Problem and the 0/1 Knapsack Problem?

easy

A. In Unbounded Knapsack, items can be chosen multiple times; in 0/1 Knapsack, each item can be chosen only once.

B. Unbounded Knapsack does not consider item weights, while 0/1 Knapsack does.

C. 0/1 Knapsack allows fractional items, Unbounded Knapsack does not.

D. Unbounded Knapsack always has a smaller maximum value than 0/1 Knapsack.

Solution

1. Step 1: Understand item selection rules

   In 0/1 Knapsack, each item can be selected at most once. In Unbounded Knapsack, items can be selected unlimited times.

2. Step 2: Compare problem constraints

   Unbounded Knapsack allows multiple copies of the same item, which is the key difference from 0/1 Knapsack.

3. Final Answer:

   In Unbounded Knapsack, items can be chosen multiple times; in 0/1 Knapsack, each item can be chosen only once. -> Option A

4. Quick Check:

   Unbounded = multiple items allowed [OK]

Hint: Remember: Unbounded means unlimited item picks [OK]

Common Mistakes:

• Confusing 0/1 Knapsack with fractional knapsack
• Thinking Unbounded Knapsack disallows repeated items
• Assuming weights are ignored in Unbounded Knapsack

2. Which of the following is the correct syntax to initialize the DP array for Unbounded Knapsack in Java for capacity W?

easy

A. int[] dp = new int[W];

B. int dp = new int[W];

C. int[] dp = new int[W+1];

D. int dp[] = new int[W-1];

Solution

1. Step 1: Understand array size for capacities

   We need an array to store max values for capacities from 0 to W, so size must be W+1.

2. Step 2: Check Java array syntax

   Correct syntax is int[] dp = new int[W+1]; which creates an integer array of size W+1.

3. Final Answer:

   int[] dp = new int[W+1]; -> Option C

4. Quick Check:

   Array size = W+1 for capacities 0 to W [OK]

Hint: DP array size = capacity + 1 for indexing [OK]

Common Mistakes:

• Using incorrect array size (W or W-1)
• Wrong Java array declaration syntax
• Declaring dp as int instead of int[]

3. What is the output of the following Java code snippet for Unbounded Knapsack?

int[] wt = {2, 3, 4};
int[] val = {15, 20, 30};
int W = 7;
int[] dp = new int[W+1];
for (int i = 0; i <= W; i++) {
    for (int j = 0; j < wt.length; j++) {
        if (wt[j] <= i) {
            dp[i] = Math.max(dp[i], dp[i - wt[j]] + val[j]);
        }
    }
}
System.out.println(dp[W]);

medium

A. 50

B. 75

C. 85

D. 90

Solution

1. Step 1: Understand DP array filling

   For each capacity i from 0 to 7, we try all items and update dp[i] with max value including unlimited items.

2. Step 2: Calculate dp values step-by-step

   dp[0]=0; dp[1]=0; dp[2]=max(0, dp[0]+15)=15; dp[3]=max(0, dp[1]+15, dp[0]+20)=20; dp[4]=max(0, dp[2]+15, dp[1]+20, dp[0]+30)=30; dp[5]=max(dp[3]+15=35, dp[2]+20=35, dp[1]+30=30)=35; dp[6]=max(dp[4]+15=45, dp[3]+20=40, dp[2]+30=45)=45; dp[7]=max(dp[5]+15=50, dp[4]+20=50, dp[3]+30=50)=50.

3. Step 3: Recalculate carefully for correct max

   Rechecking dp[7]: dp[7] = max(dp[7], dp[7-2]+15=dp[5]+15=35+15=50, dp[7-3]+20=dp[4]+20=30+20=50, dp[7-4]+30=dp[3]+30=20+30=50) = 50.

4. Final Answer:

   50 -> Option A

5. Quick Check:

   Max value for W=7 is 50 [OK]

Hint: Trace dp array updates for each capacity [OK]

Common Mistakes:

• Miscomputing dp values for capacities
• Ignoring multiple item picks
• Mixing up weights and values

4. Identify the bug in this Unbounded Knapsack Java code snippet:

int[] wt = {1, 3, 4};
int[] val = {10, 40, 50};
int W = 6;
int[] dp = new int[W+1];
for (int i = 0; i < W; i++) {
    for (int j = 0; j < wt.length; j++) {
        if (wt[j] <= i) {
            dp[i] = Math.max(dp[i], dp[i - wt[j]] + val[j]);
        }
    }
}
System.out.println(dp[W]);

medium

A. dp array size should be W, not W+1

B. Loop should run i <= W, not i < W

C. Condition should be wt[j] < i, not wt[j] <= i

D. Inner loop should start from 1, not 0

Solution

1. Step 1: Check loop range for capacity i

   The outer loop runs from i=0 to i<W, so it stops at i=5, missing capacity W=6.

2. Step 2: Correct loop condition

   To include capacity W=6, loop should run i <= W, i.e., i from 0 to 6 inclusive.

3. Final Answer:

   Loop should run i <= W, not i < W -> Option B

4. Quick Check:

   Loop must cover capacity W [OK]

Hint: Loop to W inclusive for full capacity coverage [OK]

Common Mistakes:

• Using i < W misses last capacity
• Wrong dp array size causing index errors
• Incorrect condition in if statement

5. Given weights wt = {1, 3, 4}, values val = {10, 40, 50}, and capacity W = 7, what is the maximum value achievable using the Unbounded Knapsack approach?

hard

A. 140

B. 120

C. 110

D. 90

Solution

1. Step 1: Initialize dp array and compute values

   dp[0]=0; For each capacity i from 1 to 7, calculate max value by trying all items multiple times.

2. Step 2: Calculate dp values stepwise

   dp[1]=max(dp[1], dp[0]+10)=10; dp[2]=max(dp[2], dp[1]+10)=20; dp[3]=max(dp[3], dp[0]+40, dp[2]+10)=40; dp[4]=max(dp[4], dp[1]+40, dp[0]+50, dp[3]+10)=50; dp[5]=max(dp[5], dp[2]+40, dp[1]+50, dp[4]+10)=60; dp[6]=max(dp[6], dp[3]+40, dp[2]+50, dp[5]+10)=80; dp[7]=max(dp[7], dp[4]+40, dp[3]+50, dp[6]+10)=90.

3. Step 3: Recalculate carefully for max value

   Check dp[7]: dp[7]=max(dp[7], dp[6]+10=80+10=90, dp[4]+40=50+40=90, dp[3]+50=40+50=90) = 90. But we can try combinations: 3*3 + 1*1 weights = 3+3+1=7, values = 40+40+10=90; or 4+3 weights = 7, values=50+40=90. So max is 90.

4. Final Answer:

   90 -> Option D

5. Quick Check:

   Max value for W=7 is 90 [OK]

Hint: Try all item combos for each capacity [OK]

Common Mistakes:

• Not considering multiple item picks
• Miscomputing dp values for capacities
• Ignoring best combination of items