Unbounded Knapsack Fundamentals

In the unbounded knapsack problem, each item can be used an unlimited number of times, unlike the 0/1 knapsack where each item is used at most once. This difference requires two key implementation changes:

1. When iterating through the knapsack capacity, we must iterate forward (from small to large capacities) to allow repeated use of items.
2. The DP array size is defined as capacity + 1 to accommodate all capacities from 0 to the target.

#include <iostream>
#include <vector>
using namespace std;

int unboundedKnapsackMaxValue(vector<int>& weights, vector<int>& values, int capacity) {
    vector<int> dp(capacity + 1, 0);
    
    // Iterate through all capacities
    for (int cap = 0; cap <= capacity; cap++) {
        // Try each item
        for (int idx = 0; idx < weights.size(); idx++) {
            if (cap >= weights[idx]) {
                dp[cap] = max(dp[cap], dp[cap - weights[idx]] + values[idx]);
            }
        }
    }
    return dp[capacity];
}

int main() {
    int itemCount, maxCapacity;
    cin >> itemCount >> maxCapacity;
    
    vector<int> itemWeights(itemCount);
    vector<int> itemValues(itemCount);
    
    for (int i = 0; i < itemCount; i++) {
        cin >> itemWeights[i] >> itemValues[i];
    }
    
    int result = unboundedKnapsackMaxValue(itemWeights, itemValues, maxCapacity);
    cout << result << endl;
    
    return 0;
}

518. Coin Change II (Counting Combinations)

This problem asks for the number of combinations (order doesn't matter) to make up a target amount using given coin denominations. It's a variation of the unbounded knapsack problem where we count ways rather than maximize value.

Key implementation details:

1. Initialize dp[0] = 1 (one way to make amount 0: use no coins).
2. The ietration order is crucial for counting combinations vs permutations.

Iteration Rule:

• For combinations (order doesn't matter): Outer loop iterates through items (coins), inner loop iterates through capacities.
• For permutations (order matters): Outer loop iterates through capacities, inner loop iterates through items.

Since this problem requires combinations, we use items-outer, capacities-inner order.

class Solution {
public:
    int change(int targetAmount, vector<int>& coins) {
        vector<int> dp(targetAmount + 1, 0);
        dp[0] = 1;
        
        // Outer loop: coins (items)
        for (int coinIdx = 0; coinIdx < coins.size(); coinIdx++) {
            int coinValue = coins[coinIdx];
            // Inner loop: capacities
            for (int currentAmount = coinValue; currentAmount <= targetAmount; currentAmount++) {
                dp[currentAmount] += dp[currentAmount - coinValue];
            }
        }
        return dp[targetAmount];
    }
};

377. Combination Sum IV (Counting Permutations)

This problem is similar but counts permutations (different sequences count as different combinations). The iteration order must be revresed compared to the coin change problem.

Important considerations:

1. Initialize dp[0] = 1.
2. Add overflow protection since intermediate sums might exceed integer limits.

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned int> dp(target + 1, 0);
        dp[0] = 1;
        
        // Outer loop: capacities (for permutations)
        for (int currentSum = 0; currentSum <= target; currentSum++) {
            // Inner loop: numbers (items)
            for (int idx = 0; idx < nums.size(); idx++) {
                int num = nums[idx];
                if (currentSum >= num) {
                    dp[currentSum] += dp[currentSum - num];
                }
            }
        }
        return dp[target];
    }
};

Note: Using unsigned int helps avoid overflow issues in many cases, but for strict overflow protection, you can add a check: if (dp[currentSum] > INT_MAX - dp[currentSum - num]) break;

70. Climbing Stairs (Advanced Version)

The advanced climbing stairs problem asks: In how many ways can you reach the nth step if you can climb 1 too m steps at a time? This is essentially a permutation counting problem with step sizes as items.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int totalSteps, maxStepSize;
    cin >> totalSteps >> maxStepSize;
    
    vector<int> dp(totalSteps + 1, 0);
    dp[0] = 1;  // One way to be at step 0
    
    // Outer loop: current step (capacity)
    for (int currentStep = 1; currentStep <= totalSteps; currentStep++) {
        // Inner loop: possible step sizes (items)
        for (int stepSize = 1; stepSize <= maxStepSize; stepSize++) {
            if (currentStep >= stepSize) {
                dp[currentStep] += dp[currentStep - stepSize];
            }
        }
    }
    
    cout << dp[totalSteps] << endl;
    return 0;
}

This solution counts all permutations of step sequences that reach the target, making it analogous to the combination sum IV problem with step sizes as the item set.