HDU 3033 I love sneakers! 分組背包另解：滾動數組優化空間

題目回顧

k 組物品，每組至少選一件，總花費不超過 m，最大化價值。同 ID 210618 題，本文提供空間優化寫法。

狀態定義與轉移

• `dp[i][j]`：前 i 組花費 j 最大價值
• 轉移：`dp[i][j] = max( dp[i][j-cost]+val, dp[i-1][j-cost]+val )`
• 初始化：`dp[0][*]=0`，其餘 `-1`

空間優化：二維 → 一維滾動

觀察轉移只依賴 `i` 和 `i-1`，可用兩個一維數組滾動：

vector prev(m+1, -1), cur(m+1, -1);
prev.assign(m+1, 0); // 第0組初始化

for (int i = 1; i <= k; i++) {
    fill(cur.begin(), cur.end(), -1);
    for (auto &item : group[i]) {
        for (int v = m; v >= item.cost; v--) {
            if (cur[v - item.cost] != -1)
                cur[v] = max(cur[v], cur[v - item.cost] + item.val);
            if (prev[v - item.cost] != -1)
                cur[v] = max(cur[v], prev[v - item.cost] + item.val);
        }
    }
    swap(prev, cur);
}
int ans = *max_element(prev.begin(), prev.end());

完整代碼（含輸入處理）

#include <bits/stdc++.h>
using namespace std;

struct Item { int cost, val; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, k;
    while (cin >> n >> m >> k) {
        vector> groups(k+1);
        for (int i = 0; i < n; i++) {
            int g, c, v; cin >> g >> c >> v;
            groups[g].push_back({c, v});
        }
        
        vector dp(m+1, -1), ndp(m+1);
        fill(dp.begin(), dp.end(), 0); // dp[0][*] = 0
        
        for (int i = 1; i <= k; i++) {
            fill(ndp.begin(), ndp.end(), -1);
            for (auto &it : groups[i]) {
                for (int v = m; v >= it.cost; v--) {
                    if (ndp[v - it.cost] != -1)
                        ndp[v] = max(ndp[v], ndp[v - it.cost] + it.val);
                    if (dp[v - it.cost] != -1)
                        ndp[v] = max(ndp[v], dp[v - it.cost] + it.val);
                }
            }
            dp.swap(ndp);
        }
        
        int ans = *max_element(dp.begin(), dp.end());
        if (ans < 0) cout << "Impossible\n";
        else cout << ans << '\n';
    }
    return 0;
}

優化要點總結

1. 滾動數組：空間從 O(k×m) 降為 O(m)
2. vector 替換靜態數組：動態適應 m 大小，避免棧溢出
3. fill + swap：高效重置與交換，無需 `memset`
4. 範圍 for 遍歷組內物品：代碼更簡潔安全

此寫法保持邏輯清晰，空間效率更高，適合大數據限制場景，是分組背包「至少選一」變體的工程化實現參考。