Unbounded Knapsack Problem

In the classic 0/1 Knapsack problem, each item can be selected at most once. The Unbounded Knapsack problem modifies this constraint: each item can be chosen an unlimited number of times. Consider a knapsack with a maximum capacity of 4, and the following items:

The core difference in implementation lies in the traversal direction of the inner loop. In the 0/1 Knapsack, the capacity loop iterates backward to prevent reusing the same item:

for (int i = 0; i < weights.size(); ++i) {
    for (int c = maxCapacity; c >= weights[i]; --c) {
        dp[c] = max(dp[c], dp[c - weights[i]] + profits[i]);
    }
}

To allow unlimited selections, the capacity loop must iterate forward:

// Items first, then capacity
for (int i = 0; i < weights.size(); ++i) {
    for (int c = weights[i]; c <= maxCapacity; ++c) {
        dp[c] = max(dp[c], dp[c - weights[i]] + profits[i]);
    }
}

An important property of the pure Unbounded Knapsack problem is that the nesting order of the two loops does not affect the final maximum value. Swapping the loops yields the same result:

// Capacity first, then items
for (int c = 0; c <= maxCapacity; ++c) {
    for (int i = 0; i < weights.size(); ++i) {
        if (c >= weights[i]) {
            dp[c] = max(dp[c], dp[c - weights[i]] + profits[i]);
        }
    }
}

However, when the problem shifts from finding the maximum value to counting the number of ways to fill the knapsack, the loop order becomes extremely critical. It dictates whether we count combinations or permutations.

Counting Combinations: Coin Change II

Given an array of coin denominations and a target amount, determine the number of distinct combinations that make up that amount. Each denomination can be used infinitely.

Since the problem asks for combinations, the order of coins does not matter (e.g., 2+2+1 is the same as 1+2+2).

• DP Definition: dp[t] represents the number of combinations to form amount t.
• Recurrence: dp[t] += dp[t - coin]
• Initialization: dp[0] = 1. There is exactly one way to make amount 0 (by choosing nothing). If dp[0] were 0, all subsequent states would remain 0.

To ensure we count combinations and not permutations, we must iterate over the coins (items) in the outer loop and the target amounts (capacity) in the inner loop. This guarantees that for a specific amount, coins are considered in a fixed order, preventing permutations of the same set from being counted multiple times.

int change(int target, vector<int>& denominations) {
    vector<int> dp(target + 1, 0);
    dp[0] = 1;
    for (int coin : denominations) {
        for (int t = coin; t <= target; ++t) {
            dp[t] += dp[t - coin];
        }
    }
    return dp[target];
}

Counting Permutations: Combination Sum IV

Given an array of distinct integers and a target integer, return the number of possible combinations that add up to the target. Despite the name, the problem requires counting permutations, where different sequences are counted as different combinations.

To count permutations, the loop order must be inverted. The outer loop iterates over the target sums (capacity), and the inner loop iterates over the numbers (items). This way, for each capacity, we consider all available numbers, allowing different arrangements of the same numbers to be counted separately.

• DP Definition: dp[t] represents the number of permutations to form sum t.
• Recurrence: dp[t] += dp[t - num]
• Initialization: dp[0] = 1

int combinationSum4(vector<int>& nums, int target) {
    vector<int> dp(target + 1, 0);
    dp[0] = 1;
    for (int t = 1; t <= target; ++t) {
        for (int num : nums) {
            if (t >= num) {
                dp[t] += dp[t - num];
            }
        }
    }
    return dp[target];
}