HDU2639 Bone Collector II（01背包第k优解）

March 10, 2016

题目链接

01 背包的第 k 优解，再加一个维度。

就是用 dp[j][k]代表容量为 j 时第 k 大的价值。那么在内层循环再遍历一次 k，每次遍历中将“取”和“不取”两种情况放在一个数组里，遍历完 k 之后对这个数组排序去重，然后根据顺序更新 dp[j][k]。

#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include <vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[1005][1005];
int v[1005], w[1005];
int vec[100005];
bool cmp(int x, int y){
    return x>y;
}
int main(){
    //freopen("a.txt", "r", stdin);
    int n, W, k, t;
    cin >> t;
    while(t--){
        memset(dp, 0, sizeof(dp));
        memset(vec, 0, sizeof(vec));
        scanf("%d %d %d", &n, &W, &k);
        for(int i = 1; i <= n; i++)
            scanf("%d", &v[i]);
        for(int i = 1; i <= n; i++)
            scanf("%d", &w[i]);
        for(int i = 1; i <= n; i++){
            for(int j = W; j >= w[i]; j--){
                int cnt = 0;
                for(int th = 1; th <= k; th++){
                    vec[cnt++] = dp[j][th];
                    vec[cnt++] = dp[j-w[i]][th] + v[i];
                }
                sort(vec, vec+cnt, cmp);
                cnt = unique(vec, vec+cnt) - vec;  //去重
                for(int th = 1; th <= min(cnt, k); th++)
                    dp[j][th] = vec[th-1];
            }
        }
        cout << dp[W][k] << endl;
    }
    return 0;
}

这种算法是 748MS，注意到 35 和 36 两行的 STL 的使用耗时太多，观察 32 和 33 两行的代码，其中 dp[j][th]是递减的，dp[j-w[i]][th]也是递减的，所以用两个数组分别存下这两组数，然后在 O（n）的时间就可以求出。节省了 STL 的时间。

这种方法只有 109MS。

#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include <vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[1005][1005];
int v[1005], w[1005];
int s1[100005];
int s2[100005];
int main(){
    //freopen("a.txt", "r", stdin);
    int n, W, k, t;
    cin >> t;
    while(t--){
        memset(dp, 0, sizeof(dp));
        scanf("%d %d %d", &n, &W, &k);
        for(int i = 1; i <= n; i++)
            scanf("%d", &v[i]);
        for(int i = 1; i <= n; i++)
            scanf("%d", &w[i]);
        for(int i = 1; i <= n; i++){
            for(int j = W; j >= w[i]; j--){
                for(int th = 1; th <= k; th++){
                    s1[th-1] = dp[j][th];
                    s2[th-1] = dp[j-w[i]][th] + v[i];
                }
                s1[k] = s2[k] = -1;
                int cnt = 1, cnt1 = 0, cnt2 = 0;
                while(cnt<=k && (s1[cnt1]!=-1 || s2[cnt2]!=-1)){
                    if(s1[cnt1]>s2[cnt2])
                        dp[j][cnt] = s1[cnt1++];
                    else dp[j][cnt] = s2[cnt2++];
                    if(dp[j][cnt] != dp[j][cnt-1]) cnt++;
                }
            }
        }
        cout << dp[W][k] << endl;
    }
    return 0;
}