HDU 3466 Proud Merchants：01 背包 + 貪心排序

HDU 3466 - 01 背包變種：購買門檻限制

N 個商品，價格 P_i，最低購買金額 Q_i（持有金額 ≥ Q_i 才能買），價值 V_i。初始資金 M。求最大總價值。N ≤ 500, M ≤ 5000。

關鍵洞察：按 (Q-P) 排序

商品 i 需要當前金額 ≥ Q_i，買完剩 money - P_i。定義「門檻盈餘」D_i = Q_i - P_i。若 D_i < D_j，買 i 後更容易滿足 j 的門檻。故按 D_i 升序處理，保證可行性不遺漏最優解。

DP 定義

dp[j] = 花費恰好 j 金額（或 ≤j）可獲得的最大價值。標準 01 背包逆序更新：

for (int i=1; i<=n; ++i)
    for (int j=M; j>=a[i].q; --j)  // 必須從 Q_i 開始，因買前需 ≥ Q_i
        dp[j] = max(dp[j], dp[j - a[i].p] + a[i].v);

完整代碼

struct Item { int p, q, v; } a[510];
int dp[5010];
bool cmp(Item a, Item b) { return a.q - a.p < b.q - b.p; }
int main() {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        for (int i=1; i<=n; ++i) scanf("%d%d%d", &a[i].p, &a[i].q, &a[i].v);
        sort(a+1, a+n+1, cmp);
        memset(dp, 0, sizeof(dp));
        for (int i=1; i<=n; ++i)
            for (int j=m; j>=a[i].q; --j)
                dp[j] = max(dp[j], dp[j - a[i].p] + a[i].v);
        printf("%d\n", dp[m]);
    }
}

為什麼從 q 開始而不是 p？

狀態 dp[j] 代表「當前擁有 j 金額」的最大價值。買商品 i 需前置條件 j ≥ Q_i，買後剩 j - P_i，轉移自 dp[j-P_i]。若從 P_i 開始會包含 j < Q_i 的非法狀態。

複雜度

O(N M) = 2.5e6 操作，極快。排序 O(N log N) 可忽略。