HDU 2126 買紀念品：0-1 背包求最大種類數與方案數

題目大意

有 n 種紀念品，每種價格 w[i]，擁有 m 元錢。每種最多買一件。求：

1. 最多能買幾種不同紀念品（即最大件數 K）？
2. 在買 K 種的前提下，共有多少種購買方案（S）？

若買不起任何紀念品，輸出 Sorry, you can't buy anything.

範例

輸入：
2
4 7
1 2 3 4
4 0
1 2 3 4

輸出：
You have 2 selection(s) to buy with 3 kind(s) of souvenirs.
Sorry, you can't buy anything.

解題思路：0-1 背包變體

狀態定義：dp[j][0] 表示花費 j 元能買到的最大件數；dp[j][1] 表示達成該最大件數的方案數。

狀態轉移

對每件物品 i，從 m 遞減到 w[i]：

• 若 dp[j-w[i]][0] + 1 > dp[j][0]：
  更新最大件數 dp[j][0] = dp[j-w[i]][0] + 1，方案數 dp[j][1] = dp[j-w[i]][1]。
• 若 dp[j-w[i]][0] + 1 == dp[j][0]：
  方案數累加 dp[j][1] += dp[j-w[i]][1]。

初始化與邊界

• dp[0][0] = 0, dp[0][1] = 1（花 0 元買 0 件有 1 種方案）。
• 其餘 dp[j][0] = -INF, dp[j][1] = 0。
• 若最小價格 min_w > m，直接輸出買不到。

完整代碼（C++）

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int w[55], dp[505][2];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        int min_w = INF;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &w[i]);
            min_w = min(min_w, w[i]);
        }
        if (min_w > m) {
            puts("Sorry, you can't buy anything.");
            continue;
        }
        for (int j = 0; j <= m; ++j) dp[j][0] = -INF, dp[j][1] = 0;
        dp[0][0] = 0; dp[0][1] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = m; j >= w[i]; --j) {
                if (dp[j-w[i]][0] + 1 > dp[j][0]) {
                    dp[j][0] = dp[j-w[i]][0] + 1;
                    dp[j][1] = dp[j-w[i]][1];
                } else if (dp[j-w[i]][0] + 1 == dp[j][0]) {
                    dp[j][1] += dp[j-w[i]][1];
                }
            }
        }
        printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",
               dp[m][1], dp[m][0]);
    }
    return 0;
}

複雜度分析

• 時間：O(T * n * m)，n ≤ 30, m ≤ 500，極快。
• 空間：O(m)。

關鍵點總結

1. 雙維度 DP 同時維護「最大件數」與「方案數」。
2. 逆序遍歷 j 保證 0-1 特性（每件最多用一次）。
3. 方案數累加時注意 long long 防溢出（題目說 32 位有符號整數範圍內）。