Unbounded Knapsack Problem in DSA C

Mental Model

You can pick items multiple times to fill a bag with maximum value without exceeding its weight limit.

Analogy: Imagine you have a backpack and unlimited candies of different weights and values. You want to fill your backpack to get the most tasty candies without breaking it.

Capacity: 5
Items: [weight: 1, value: 10], [weight: 3, value: 40], [weight: 4, value: 50]

Bag capacity -> 5
Items ->
[1,10] -> [3,40] -> [4,50]

Goal: Maximize value by choosing items any number of times.

Dry Run Walkthrough

Input: items: weights = [1, 3, 4], values = [10, 40, 50], capacity = 5

Goal: Find the maximum value we can get by picking items any number of times without exceeding capacity 5

Step 1: Initialize dp array with 0 for capacity 0 to 5

dp = [0, 0, 0, 0, 0, 0]

Why: Start with no items chosen, so max value is 0 for all capacities

Step 2: For capacity 1, check items: weight 1 fits, update dp[1] = max(dp[1], dp[1-1] + 10) = 10

dp = [0, 10, 0, 0, 0, 0]

Why: Choosing item with weight 1 and value 10 fits capacity 1

Step 3: For capacity 2, item weight 1 fits: dp[2] = max(dp[2], dp[2-1] + 10) = 20

dp = [0, 10, 20, 0, 0, 0]

Why: We can pick item with weight 1 twice to fill capacity 2

Step 4: For capacity 3, check items: weight 1 fits dp[3] = max(0, dp[2]+10)=30; weight 3 fits dp[3] = max(30, dp[0]+40)=40

dp = [0, 10, 20, 40, 0, 0]

Why: Choosing item with weight 3 and value 40 is better than three times item 1

Step 5: For capacity 4, check items: weight 1 fits dp[4] = max(0, dp[3]+10)=50; weight 3 fits dp[4] = max(50, dp[1]+40)=50; weight 4 fits dp[4] = max(50, dp[0]+50)=50

dp = [0, 10, 20, 40, 50, 0]

Why: Picking item with weight 4 and value 50 or item 1 + item 3 both give max 50

Step 6: For capacity 5, check items: weight 1 fits dp[5] = max(0, dp[4]+10)=60; weight 3 fits dp[5] = max(60, dp[2]+40)=60; weight 4 fits dp[5] = max(60, dp[1]+50)=60

dp = [0, 10, 20, 40, 50, 60]

Why: Best is picking item 1 five times or item 3 + item 1 or item 4 + item 1

Result:

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

Annotated Code

DSA C

#include <stdio.h>

int unboundedKnapsack(int capacity, int weights[], int values[], int n) {
    int dp[capacity + 1];
    for (int i = 0; i <= capacity; i++) {
        dp[i] = 0; // initialize dp array
    }

    for (int w = 1; w <= capacity; w++) {
        for (int i = 0; i < n; i++) {
            if (weights[i] <= w) {
                int val = dp[w - weights[i]] + values[i];
                if (val > dp[w]) {
                    dp[w] = val; // update max value for capacity w
                }
            }
        }
    }
    return dp[capacity];
}

int main() {
    int weights[] = {1, 3, 4};
    int values[] = {10, 40, 50};
    int capacity = 5;
    int n = sizeof(weights) / sizeof(weights[0]);

    int maxValue = unboundedKnapsack(capacity, weights, values, n);
    printf("Maximum value for capacity %d is %d\n", capacity, maxValue);
    return 0;
}

for (int i = 0; i <= capacity; i++) { dp[i] = 0; }

initialize dp array with 0 for all capacities

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

iterate over all capacities from 1 to capacity

for (int i = 0; i < n; i++) {

check each item for current capacity

if (weights[i] <= w) {

item fits in current capacity

int val = dp[w - weights[i]] + values[i];

calculate value if we include this item

if (val > dp[w]) { dp[w] = val; }

update dp[w] if new value is better

return dp[capacity];

return max value for full capacity

Output

Maximum value for capacity 5 is 60

Complexity Analysis

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

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

vs Alternative: Compared to recursive exponential approach, this dynamic programming solution is much faster and uses less time by storing intermediate results.

Edge Cases

capacity = 0

returns 0 because no items can be chosen

DSA C

for (int i = 0; i <= capacity; i++) { dp[i] = 0; }

items with weight greater than capacity

those items are ignored because they don't fit

DSA C

if (weights[i] <= w) {

single item with weight 1

dp fills with multiples of that item's value

DSA C

int val = dp[w - weights[i]] + values[i];

When to Use This Pattern

When you can use items unlimited times to maximize value within a weight limit, reach for the Unbounded Knapsack pattern because it handles repeated item choices efficiently.

Common Mistakes

Mistake: Using 2D dp array like 0/1 knapsack and not allowing repeated items
Fix: Use 1D dp array and update dp[w] considering dp[w - weight[i]] to allow multiple picks

Summary

Finds max value by picking items unlimited times without exceeding capacity

Use when items can be chosen multiple times and you want max total value within weight limit

Key insight: dp[w] depends on dp[w - weight[i]] allowing repeated item inclusion