一、Problem Practice

1.1 Word Break

Problem Link: . - LeetCode

class Solution {
public:
    bool existsInDict(const vector<string>& dictionary, const string& target) {
        for (const auto& word : dictionary) {
            if (word == target) return true;
        }
        return false;
    }
    
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.length() + 1, false);
        dp[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                string segment = s.substr(j, i - j);
                if (existsInDict(wordDict, segment) && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
};

The recursive logic here is relatively intuitive, but the iteration pattern differs from previous problems. This problem involves decomposing substrings progressively, and examining the debug output reveals that the traversal shrinks from the largest possible segments downward.

1.2 Multiple Knapsack

Problem Link: 56. Carry Mineral Resources (Round 8 Mock Interview)

This can be effectively converted into a 0/1 Knapsack problem:

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

int main() {
    int capacity, itemCount;
    cin >> capacity >> itemCount;
    
    vector<int> weights(itemCount, 0);
    vector<int> values(itemCount, 0);
    vector<int> counts(itemCount, 0);
    
    for (int i = 0; i < itemCount; i++) cin >> weights[i];
    for (int i = 0; i < itemCount; i++) cin >> values[i];
    for (int i = 0; i < itemCount; i++) cin >> counts[i];
    
    for (int i = 0; i < (int)counts.size(); i++) {
        while (counts[i] > 1) {
            weights.push_back(weights[i]);
            values.push_back(values[i]);
            counts[i]--;
        }
    }
    
    vector<int> dp(capacity + 1, 0);
    
    for (int i = 0; i < (int)weights.size(); i++) {
        for (int j = capacity; j >= weights[i]; j--) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    cout << dp[capacity] << endl;
    
    return 0;
}

二、Knapsack Problem Summary

The following content draws from: Code Thinking Records

When analyzing knapsack problems, we follow these five key steps:

1. Define the dp array (dp table) and the meaning of its indices
2. Determine the recurrence formula
3. Initialize the dp array
4. Establish the iteration order
5. Derive the dp array with examples

Knapsack Recurrence Formulas

For filling the bag or maximizing capacity:

dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

Related problems:

• Dynamic Programming: 416. Partition Equal Subset Sum
• Dynamic Programming: 1049. Last Stone Weight II

For counting the number of ways to fill the bag:

dp[j] += dp[j - nums[i]];

Related problems:

• Dynamic Programming: 494. Target Sum
• Dynamic Programming: 518. Coin Change II
• Dynamic Programming: 377. Combination Sum IV
• Dynamic Programming: 70. Climbing Stairs (Advanced - Complete Knapsack)

For maximizing bag value:

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

Related problem:

• Dynamic Programming: 474. Ones and Zeroes

For minimizing the number of items to fill the bag:

dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

Related problems:

• Dynamic Programming: 322. Coin Change
• Dynamic Programming: 279. Perfect Squares

Iteration Order

0/1 Knapsack

For 2D dp array implementations of 0/1 knapsack, iterating over items first or capacity first both work, and the inner loop traverses in ascending order.

For 1D dp array (space-optimized) implementations, you must iterate over items first, then capacity, with the inner loop traversing in descending order.

There's a significant difference in iteration order between 2D and 1D dp array implementations. This distinction is crucial!

Complete Knapsack

For pure complete knapsack with 1D dp array, both iteration orders work, and the inner loop traverses in ascending order.

However, for problems with variations, the loop order makes a substantial difference.

For combinations (order doesn't matter): iterate over items in the outer loop, then capacity in the inner loop.

For permutations (order matters): iterate over capacity in the outer loop, then items in the inner loop.

Related problems:

• Combinations: Dynamic Programming: 518. Coin Change II
• Permutations: Dynamic Programming: 377. Combination Sum IV, Dynamic Programming: 70. Climbing Stairs (Advanced - Complete Knapsack)

For minimum count problems, loop order doesn't matter:

• Minimum count: Dynamic Programming: 322. Coin Change, Dynamic Programming: 279. Perfect Squares

For knapsack problems, the recurrence formula is typically the easier part. The real challenge lies in the iteration order. Mastering the traversal patterns is what constitutes true understanding of knapsack problems.

Key Takeaways

This summary provides a comprehensive overview of knapsack problems, focusing on two critical aspects: recurrence formulas and iteration orders, all illustrated with LeetCode problems.

Each point includes corresponding problem links for reference.

For those interested in multiple knapsack problems, refer to the dedicated article on the topic. Multiple knapsack rarely appears in interviews and isn't a major focus on LeetCode.

Mastering the concepts covered here demonstrates a deep understanding of knapsack problems—sufficient preparation for any knapsack-related interview questions.

Knapsack Problem Summary: