hdu 2639 Bone Collector II (0/1背包)

点击打开链接hdu 2639

思路: 0/1背包求第k优解
分析:
1 其基本思想是,将每个状态都表示成有序队列,将状态转移方程中的 max/min 转 化成有序队列的合并。
2 这里仍然以 01 背包为例讲解一下。
首先看 01 背包求最优解的状态转移方程: F [i, v] = max{F [i − 1, v], F [i − 1, v −Ci ] + Wi }。如果要求第 K 优解,那么状态 F [i, v] 就应该是一个大小为 K 的队列F [i, v, 1 . . . K]。其中 F [i, v, k] 表示前 i 个物品中,背包大小为 v 时,第 k 优解的值。这里也可以简单地理解为在原来的方程中加了一维来表示结果的优先次序。显然f [i, v, 1 . . . K] 这 K 个数是由大到小排列的,所以它可看作是一个有序队列。然后原方程就可以解释为: F [i, v] 这个有序队列是由 F [i − 1, v] 和 F [i − 1,v −Ci ] + Wi 这两个有序队列合并得到的。前者 F [i − 1][V ] 即 F [i − 1, v, 1 . . . K],后者F [i − 1,v − Ci ] + Wi 则理解为在 F[i − 1,v − Ci , 1 . . . K] 的每个数上加上 Wi 后得到的有序队列。合并这两个有序队列并将结果的前 K 项储存到 f [i, v, 1 . . . K] 中的复杂度是O(K)。最后的第 K 优解的答案是 F [N, V, K]。总的时间复杂度是 O(V N K)。
3 这边的难点就是在于合并，但是只要懂得了归并排序的这边都不难理解，还有要注意的一个地方就是题目说了把相同的值看成是一样的，所以这边的1～k的值是严格的递减，在合并的时候注意

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAX = 110;
const int MAXN = 1010;

int n , sumv , k;
int v[MAX] , w[MAX] , dp[MAXN][MAX];

int solve(){
    int arrOne[MAX] , arrTwo[MAX];
    memset(dp , 0 , sizeof(dp));
    for(int i = 1 ; i <= n ; i++){
        for(int j = sumv ; j >= v[i] ; j--){
            for(int cnt = 1 ; cnt <= k ; cnt++){
                arrOne[cnt] = dp[j][cnt]; 
                arrTwo[cnt] = dp[j-v[i]][cnt]+w[i]; 
            }
            int a , b , c;
            a = b = c = 1;
            // 归并排序
            while(c <= k && a <= k && b <= k){
                 if(arrOne[a] > arrTwo[b]) 
                     dp[j][c] = arrOne[a++];
                 else
                     dp[j][c] = arrTwo[b++];
                 // 注意值相同的算一个
                 if(dp[j][c] != dp[j][c-1])
                     c++;
            }
            while(a <= k && c <= k){
                dp[j][c] = arrOne[a++];
                // 注意值相同的算一个
                if(dp[j][c-1] != dp[j][c])
                    c++;
            }
            while(b <= k && c <= k){
                dp[j][c++] = arrTwo[b++];
                // 注意值相同的算一个
                if(dp[j][c-1] != dp[j][c])
                    c++;
            }
        }
    }
    return dp[sumv][k];
}

int main(){
    int Case;
    scanf("%d" , &Case);
    while(Case--){
         scanf("%d%d%d" , &n , &sumv , &k); 
         for(int i = 1 ; i <= n ; i++)
             scanf("%d" , &w[i]);
         for(int i = 1 ; i <= n ; i++)
             scanf("%d" , &v[i]);
         printf("%d\n" , solve()); 
    }
    return 0;
}