NYOJ 49 開心的小明：01 背包入門經典題

NYOJ 49 開心的小明：01 背包入門經典題

題目大意

預算 N (<30,000)，m (<25) 件物品。每件有價格 v (≤10,000) 和重要度 p (1~5)。選擇物品總價 ≤ N，最大化 ∑ v[i]*p[i]。多測試案例。

標準 01 背包

dp[j] = 花費 j 獲得的最大價值。逆序遍歷費用：

#include 
#include 
using namespace std;

int v[26], w[26], dp[30005];

int main() {
    int T; cin >> T;
    while (T--) {
        int N, m; cin >> N >> m;
        for (int i = 0; i < m; ++i) cin >> v[i] >> w[i];
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < m; ++i)
            for (int j = N; j >= v[i]; --j)
                dp[j] = max(dp[j], dp[j - v[i]] + v[i] * w[i]);
        cout << dp[N] << endl;
    }
    return 0;
}

關鍵點

• 物品價值 = 價格 × 重要度
• 逆序遍歷保證每件物品只用一次（01 背包特徵）
• m ≤ 25, N ≤ 30,000，O(mN) ≈ 75 萬操作，極快
• dp 數組大小 N+1 即可

樣例

輸入：
1
1000 5
800 2
400 5
300 5
400 3
200 2

輸出：
3900

選 400(5) + 300(5) + 200(2) = 900 元，價值 2000+1500+400=3900。

純粹的 01 背包模板題，適合初學者練手。