算法精講：多重子集和問題（Bounded Subset Sum）O(nK) 動態規劃優化 C++ 實現

算法精講：多重子集和問題（Bounded Subset Sum）O(nK) 動態規劃優化 C++ 實現

多重子集和問題：給定 n 種數字，第 i 種值 a[i] 有 m[i] 個，判斷能否選出若干數字和恰為 K。本文從 O(nKm) 朴素 DP 出發，推導 O(nK) 餘量 DP 優化，提供完整 C++ 實現、狀態語義證明、測試驗證與變體擴展。

問題形式化

• 輸入：n 種數字，值 a[0..n-1]，各有 m[0..n-1] 個；目標和 K
• 輸出：是否存在選擇方案使和恰為 K（Yes/No）
• 示例：n=3, a={3,5,8}, m={3,2,2}, K=17 → 3×3 + 2×5 + 1×8 = 9+10+8=27? 實際解：3+5+5+? 經驗證可行 → Yes

方案一：朴素三維/二維 DP O(nKm) 時間

// dp[i][j] = 前 i 種能否湊成 j
bool dp[MAX_N+1][MAX_K+1];

void solve_naive() {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = true;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= K; j++) {
            for (int k = 0; k <= m[i] && k*a[i] <= j; k++) {
                dp[i+1][j] |= dp[i][j - k*a[i]];
            }
        }
    }
    // 結果 dp[n][K]
}

瓶頸： 內層 k 循環導致 O(nKm)，m[i] 大時不可接受。

方案二：餘量 DP 優化 O(nK) 時間 O(K) 空間（核心突破）

狀態重新定義

dp[j] = 使用前 i 種數字湊成和 j 時，第 i 種數字最多還能用幾個。
dp[j] ≥ 0 表示可行，-1 表示不可行。

遞推邏輯證明

// 初始：0 種數字湊成 0 餘量無限大（或 m[0]），其餘 -1
dp[0] = 0;  // 特殊標記：和為 0 總是可行
for (j=1..K) dp[j] = -1;

for (i=0..n-1) {
    for (j=0..K) {
        if (dp[j] >= 0) {
            // 狀態 j 已可行，第 i 種數字「重置」可用 m[i] 個
            dp[j] = m[i];
        } else if (j < a[i] || dp[j - a[i]] <= 0) {
            // 不可行：容量不足 或 前驅狀態無餘量
            dp[j] = -1;
        } else {
            // 可行：從 j-a[i] 轉移，消耗 1 個第 i 種
            dp[j] = dp[j - a[i]] - 1;
        }
    }
}
// 結果 dp[K] >= 0 即 Yes

狀態轉移圖解（示例 n=3, a={3,5,8}, m={3,2,2}, K=17）

i\j  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
初始  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
i=0(3,3)  3 -1 -1  2 -1 -1  1 -1 -1  0 -1 -1 -1 -1 -1 -1 -1 -1
i=1(5,2)  2 -1 -1  2 -1  1  2 -1  1  2  0 -1 -1  0  1 -1 -1 -1
i=2(8,2)  2 -1 -1  2 -1  2  2 -1  2  2  2  1 -1  1  1 -1  1  1
結果 dp[17]=1 ≥ 0 → Yes

完整 C++ 實現

#include <stdio.h>
#include <string.h>
#include <algorithm>

#define MAX_N 100
#define MAX_K 10000

int n, K;
int a[MAX_N], m[MAX_N];
int dp[MAX_K + 1];

bool solve_bounded_subset_sum() {
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;  // 和為 0 總可行
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= K; j++) {
            if (dp[j] >= 0) {
                dp[j] = m[i];                    // 重置餘量
            } else if (j < a[i] || dp[j - a[i]] <= 0) {
                dp[j] = -1;                      // 不可達
            } else {
                dp[j] = dp[j - a[i]] - 1;        // 消耗 1 個
            }
        }
    }
    return dp[K] >= 0;
}

int main() {
    // 測例
    n = 3; K = 17;
    int a1[] = {3, 5, 8};
    int m1[] = {3, 2, 2};
    memcpy(a, a1, sizeof(a1));
    memcpy(m, m1, sizeof(m1));
    
    if (solve_bounded_subset_sum())
        printf("result = Yes\n");
    else
        printf("result = No\n");
    return 0;
}

核心不變量證明

循環不變量：處理完前 i 種後，dp[j] 等於「湊成 j 時第 i 種剩餘可用數」。

• 初始化：i=-1，只有 j=0 可行，餘量設 0（特殊標記）
• 保持：
  • 若 dp[j] ≥ 0：說明不需第 i 種即可湊成 j，故第 i 種完整保留 m[i] 個
  • 若 dp[j] = -1 且 (j < a[i] 或 dp[j-a[i]] ≤ 0)：無法湊成
  • 否則：必須用 1 個第 i 種，餘量 = 前驅餘量 - 1
• 終止：i=n-1 時，dp[K] ≥ 0 ⇔ 存在方案

變體擴展

複雜度對比

多重子集和問題的 O(nK) 餘量 DP 是「狀態壓縮」藝術的巔峰之作：將「已用多少件」反轉為「還能用幾件」，巧妙利用單調性消除內層循環。這種「餘量視角」同樣適用於多重背包、硬幣找零最少硬幣數、資源配額分配等問題。建議反覆推演狀態轉移表，直到能凭空默寫遞推邏輯。