HDU 2639 Bone Collector II：01 背包第 K 優解（去重）

HDU 2639 Bone Collector II：01 背包第 K 優解

題目大意

N ≤ 100 件骨頭，體積 V ≤ 1000，求第 K ≤ 30 大不同總價值。相同價值視為同一解，輸出嚴格遞減序列第 K 個；不足 K 輸出 0。

DP 狀態定義

dp[j][k]：體積 j 時第 k 大價值（k=1..K）。每狀態維護前 K 優解，最後答案為 dp[V][K]。

轉移與去重

• 對每件物品，倒序體積 j = V .. cost[i]。
• 合併兩組候選值：dp[j][*]（不選）與 dp[j-cost[i]][*] + val[i]（選）。
• 合併後 排序降序 + unique 去重，取前 K 存回 dp[j][1..K]。

核心程式碼（C++）

#include <bits/stdc++.h>
using namespace std;

int dp[1001][31];
int cost[101], val[101];
int tmp[62]; // 2*K 候選

bool cmp_desc(int a, int b) { return a > b; }

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, V, K; scanf("%d%d%d", &n, &V, &K);
        for (int i=1;i<=n;i++) scanf("%d", &val[i]);
        for (int i=1;i<=n;i++) scanf("%d", &cost[i]);

        memset(dp, 0, sizeof(dp));
        for (int i=1;i<=n;i++) {
            for (int j=V;j>=cost[i];j--) {
                int cnt = 0;
                for (int k=1;k<=K;k++) tmp[++cnt] = dp[j][k];
                for (int k=1;k<=K;k++) tmp[++cnt] = dp[j-cost[i]][k] + val[i];
                sort(tmp+1, tmp+cnt+1, cmp_desc);
                cnt = unique(tmp+1, tmp+cnt+1) - tmp - 1;
                for (int k=1;k<=K;k++) dp[j][k] = (k<=cnt ? tmp[k] : 0);
            }
        }
        printf("%d\n", dp[V][K]);
    }
    return 0;
}

關鍵細節

• unique 需配合排序，僅移除相鄰重複值。
• 陣列 tmp 大小 2*K+5 即夠（K≤30）。
• 初始 dp[][]=0 代表無解，0 參與比較不影響正值選取。

範例驗證

Input:
3
5 10 2
1 2 3 4 5
5 4 3 2 1
5 10 12
...
Output:
12
2
0