ZeroJudge 解題筆記：k622. [棕]0-1背包問題

作者：王一哲
日期：2025年12月2日


ZeroJudge 題目連結：k622. [棕]0-1背包問題

解題想法

標準的背包問題。用一個陣列 dp 代表各種總重量對應的最大價值總和，依序讀取每樣物品的價值 p 及重量 w，從 dp 最後一項往回檢查到 dp[w] 為止，更新每一項的最大價值總和。

題目敘述有誤，物品重量上限不是 $10^4$，是 $10^7$。由於測資中物品重量大值為 $10^7$，用 C++ 解題時，如果將 array 開在 main 之中，倒數第二筆測資會遇到記憶體區段錯誤；如果將 array 開在 main 外面，在記憶體限制為 64 MB 的條件下，理論上最大長度為 $1.6 \times 10^7$ ，但我送程解答時會遇到記憶體區段錯誤。改用 vector 才能過關。至於 Python 則是怎麼樣都過不了。

這題的物品價值上限為 $10^8$，數量上限為 $10^9$，理論上價值總和應該會超過 int 的上限。如果用 long long 儲存 dp 的資料，會超過記憶體上限。改用 int 儲存 dp 的資料才能過關。

Python 程式碼

倒數第2筆測資超出記憶體上限，最後一筆測資超時。

n, k = map(int, input().split())
weight = list(map(int, input().split()))
price = list(map(int, input().split()))
dp = [0]*(k+1)
for w, p in zip(weight, price):
    for i in range(k, w-1, -1):
        dp[i] = max(dp[i], dp[i-w] + p)
print(dp[-1])

C++ 程式碼

使用時間約為 87 ms，記憶體約為 38.4 MB，通過測試。

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

int main() {
    int n, k; scanf("%d %d", &n, &k);
    vector<int> weight (n), dp (k+1, 0);
    for(int i=0; i<n; i++) scanf("%d", &weight[i]);
    for(int i=0, w, p; i<n; i++) {
        w = weight[i];
        scanf("%d", &p);
        for(int j=k; j>=w; j--) {
            if (dp[j-w] + p > dp[j]) {
	            dp[j] = dp[j-w] + p;
	        }
        }
    }
    printf("%d\n", dp[k-1]);
    return 0;
}