HDU 2191：多重背包問題（二進制優化/單調隊列）

問題描述

經典多重背包：n 容量，m 類物品，每類有體積 c[i]、價值 v[i]、數量 b[i]。求最大價值。

二進制拆分優化 (O(V Σ log b_i))

將數量 b 拆分為 1,2,4,...,2^k,b-2^k+1 份，每份視為 01 背包物品。
代碼片段：

for (int i=1; i<=m; ++i) {
    int k = 1, cnt = b[i];
    while (k < cnt) {
        V.push_back(k * v[i]); W.push_back(k * c[i]);
        cnt -= k; k <<= 1;
    }
    if (cnt) { V.push_back(cnt * v[i]); W.push_back(cnt * c[i]); }
}
// 01 背包
for (int i=0; i=W[i]; --j)
        dp[j] = max(dp[j], dp[j-W[i]] + V[i]);

單調隊列優化 (O(V·m))

對每個餘數類 r = 0..c[i]-1，DP 狀態 dp[j] = max_{k} (dp[j-k*c] + k*v)。用單調隊列維護滑動窗口最大值，線性處理每類。

樣例代碼 (二進制拆分版)

#include 
#include 
#include 
using namespace std;
int main() {
    int T; cin >> T;
    while (T--) {
        int n, m; cin >> n >> m;
        vector V, W;
        for (int i=0, c,v,b; i> c >> v >> b;
            for (int k=1; k<=b; k<<=1) {
                V.push_back(k*v); W.push_back(k*c);
                b -= k;
            }
            if (b) { V.push_back(b*v); W.push_back(b*c); }
        }
        vector dp(n+1, 0);
        for (int i=0; i=W[i]; --j)
                dp[j] = max(dp[j], dp[j-W[i]] + V[i]);
        cout << dp[n] << endl;
    }
}