hdu 2639 Bone Collector II (dp 01背包求第k優解)

題目大意：

有n件物品，每件物品有體積和價值兩個屬性， 一個小偷帶著一個大小為v的背包，要偷這些東西，問小偷能偷的第k大的價值是多少？

思路：

這題和典型的01背包求最優解不同，是要求第k大的解，所以，最直觀的想法就是在01背包的基礎上再增加一維，用來保存前k大小的數，然後在遞推時，根據前一個狀態的前k

大小的數推出下一個階段的前k個數保存下來。

d[i][j][k], 表示取前i個物品，用j的費用，第k大價值是多少

在遞推d[i][j][1...k]時，先獲取上一個狀態d[i-1][j][1...k]遞推出來所有的值:

即集合A={dp[i-1][j][p]+w[i], 1<=p<=k}， 還有原來的值集合B={dp[i-1][j][p], 1<=p<=k}

然後把集合A和B中的前k大的值按從大到小順序賦值給d[i][j][1...k]

這一步驟可以用歸並排序中的合並方法，因為集合A和B一定是按照從大到小的順序排列的。

代碼：

[cpp]  #include<iostream>  
#include<cstdio>  
#include<cmath>  
#include<algorithm>  
#include<cstring>  
#include<vector>  
#define SQ(x) ((x)*(x))  
#define MP make_pair  
const int INF = 0x3f3f3f3f; 
const double PI = acos(-1.0); 
typedef long long int64; 
using namespace std; 
 
const int MAXN = 110; 
int n, volume, z, k; 
int c[MAXN], w[MAXN]; 
int f[1100][35]; 
int a[35], b[35]; 
 
int main(){ 
    int nCase; 
    scanf("%d", &nCase); 
    while(nCase--){ 
        scanf("%d%d%d", &n, &volume, &k); 
        for(int i=1; i<=n; ++i) 
            scanf("%d", &w[i]); 
        for(int i=1; i<=n; ++i) 
            scanf("%d", &c[i]); 
 
        memset(f, 0, sizeof(f)); 
 
        for(int i=1; i<=n; ++i){ 
            for(int v=volume; v>=c[i]; --v){ 
                int p1=0, p2=0; 
                for(int j=1; j<=k; ++j){ 
                    if(f[v][j]) b[p2++] = f[v][j]; 
                    a[p1++] = f[v-c[i]][j]+w[i]; 
                }    
                // 用歸並排序的合並方法  
                int x=0, y=0, j=1; 
                while(j<=k && (x<p1 || y<p2)){ 
                    int tmp=0; 
                    if(y>=p2 || x<p1 && a[x]>b[y]){ 
                        tmp = a[x++]; 
                    }else 
                        tmp = b[y++]; 
                    if(j==1 || tmp!=f[v][j-1]) //不能相同  
                        f[v][j++] = tmp; 
                } 
            } 
        } 
        printf("%d\n", f[volume][k]); 
    }  
    return 0; 
} 

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#define SQ(x) ((x)*(x))
#define MP make_pair
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef long long int64;
using namespace std;

const int MAXN = 110;
int n, volume, z, k;
int c[MAXN], w[MAXN];
int f[1100][35];
int a[35], b[35];

int main(){
 int nCase;
 scanf("%d", &nCase);
 while(nCase--){
  scanf("%d%d%d", &n, &volume, &k);
  for(int i=1; i<=n; ++i)
   scanf("%d", &w[i]);
  for(int i=1; i<=n; ++i)
   scanf("%d", &c[i]);

  memset(f, 0, sizeof(f));

  for(int i=1; i<=n; ++i){
   for(int v=volume; v>=c[i]; --v){
    int p1=0, p2=0;
    for(int j=1; j<=k; ++j){
     if(f[v][j]) b[p2++] = f[v][j];
     a[p1++] = f[v-c[i]][j]+w[i];
    } 
    // 用歸並排序的合並方法
    int x=0, y=0, j=1;
    while(j<=k && (x<p1 || y<p2)){
     int tmp=0;
     if(y>=p2 || x<p1 && a[x]>b[y]){
      tmp = a[x++];
     }else
      tmp = b[y++];
     if(j==1 || tmp!=f[v][j-1]) //不能相同
      f[v][j++] = tmp;
    }
   }
  }
  printf("%d\n", f[volume][k]);
 }
 return 0;
}