HDU 2660 Accepted Necklace：限制件數的 01 背包變形

HDU 2660 Accepted Necklace 題目分析

給定 N (≤20) 顆寶石，每顆有價值 a 和重量 b。必須恰好選 K 顆，總重量不超過 W (≤1000)，求最大總價值。這是經典 01 背包的「件數限制」變形：在狀態中增加一維「已選件數」。

動態規劃狀態定義

dp[v][j] 表示總重量恰為 v、已選 j 顆寶石時的最大價值。初始 dp[0][0] = 0，其餘 -∞。對每顆寶石 (val, wt)，倒序枚舉重量 v 從 W 到 wt，再枚舉件數 j 從 1 到 K：
dp[v][j] = max(dp[v][j], dp[v-wt][j-1] + val)

代碼實現

#include 
#include 
#include 
using namespace std;

struct Stone { int val, w; } s[22];
int dp[1005][22];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int N, K, W; scanf("%d%d", &N, &K);
        for (int i = 1; i <= N; ++i) scanf("%d%d", &s[i].val, &s[i].w);
        scanf("%d", &W);
        memset(dp, -0x3f, sizeof(dp));
        dp[0][0] = 0;
        for (int i = 1; i <= N; ++i) {
            for (int v = W; v >= s[i].w; --v) {
                for (int j = 1; j <= K; ++j) {
                    dp[v][j] = max(dp[v][j], dp[v - s[i].w][j-1] + s[i].val);
                }
            }
        }
        printf("%d\n", dp[W][K]);
    }
    return 0;
}

複雜度與優化

時間 O(N·W·K) ≤ 20×1000×20 = 4×10^5，空間 O(W·K) ≈ 2×10^4，極易通過。若 K 較大可用滾動數組優化空間，但本題無需。關鍵點在於「恰好 K 件」對應 dp[W][K]，而非 max_{j≤K}。若改為「至多 K 件」，輸出 max_{j≤K} dp[W][j] 即可。

舉一反三

同類「限制選取數量」的背包問題還有：HDU 1258、2553、1045、2181、2952 等，均可用相同擴維思路解決。