Unbounded Knapsack Problem in DSA Java - Time & Space Complexity

Time Complexity: Unbounded Knapsack Problem

O(n * W)

Understanding Time Complexity

We want to understand how the time needed to solve the Unbounded Knapsack Problem grows as the input size changes.

The question is: how does the number of operations increase when we have more items or a larger knapsack capacity?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int unboundedKnapsack(int W, int[] wt, int[] val, int n) {
    int[] dp = new int[W + 1];
    for (int i = 0; i <= W; i++) {
        for (int j = 0; j < n; j++) {
            if (wt[j] <= i) {
                dp[i] = Math.max(dp[i], dp[i - wt[j]] + val[j]);
            }
        }
    }
    return dp[W];
}
    

This code finds the maximum value that fits into a knapsack of capacity W, where items can be chosen unlimited times.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The nested loops where for each capacity from 0 to W, we check all n items.
• How many times: The outer loop runs W+1 times, and the inner loop runs n times for each outer iteration.

How Execution Grows With Input

As the knapsack capacity W grows, the number of operations grows roughly by multiplying W and n.

Input Size (W)	Approx. Operations (W * n)
10	10 * n
100	100 * n
1000	1000 * n

Pattern observation: Doubling the capacity roughly doubles the operations, assuming n stays the same.

Final Time Complexity

Time Complexity: O(n * W)

This means the time needed grows proportionally with both the number of items and the knapsack capacity.

Common Mistake

[X] Wrong: "Since items can be chosen unlimited times, the time complexity must be exponential because of infinite choices."

[OK] Correct: The dynamic programming approach uses a table to store results for each capacity, avoiding repeated work and keeping time proportional to n times W.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming efficiently solves problems with repeated choices, a common skill in interviews.

Self-Check

"What if we changed the problem to allow only one instance of each item? How would the time complexity change?"

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