这题和典型的01背包求最优解不同,是要求第k优解,所以,最直观的想法就是在01背包的基础上再增加一维表示第k大时的价值。
具体思路见下面的参考链接,说的很详细
参考连接:
http://laiba2004.blog.163.com/blog/static/8835120220138611342496/
http://hi.baidu.com/*00/item/1c6c44318acc8bfaa88428c7
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
const int maxn=;
const int maxv=;
const int maxk=;
int n,v,k;
int dp[maxv][maxk]; //dp[j][k]表示容量为j时,第k大的值
int w[maxn]; //价值
int vv[maxn]; //容量
//一开始tmp只开了maxk个大小,导致WA。。。因为对应的每个k,有dp[j][z]和dp[j-vv[i]][z]+w[i]两个状态,所以要开2*maxk大小
//int tmp[maxk*2];
int tmp1[maxk*];
int tmp2[maxk*];
int main()
{
int t,idx,cnt;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&v,&k);
for(int i=;i<=n;i++)
scanf("%d",&w[i]); //价值
for(int i=;i<=n;i++)
scanf("%d",&vv[i]); //容量
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++){
for(int j=v;j>=vv[i];j--){
//idx=0;
for(int z=;z<=k;z++){
tmp1[z]=dp[j][z];
tmp2[z]=dp[j-vv[i]][z]+w[i];
}
/*
sort(tmp+1,tmp+idx+1);
cnt=1;
dp[j][1]=tmp[idx];
for(int q=idx-1;q>=1&&cnt<k;q--){
if(tmp[q]!=tmp[q+1])
dp[j][++cnt]=tmp[q];
}
while(cnt<k){
dp[j][++cnt]=0;
}
*/
//其实不需要按照上面用排序,可以用开两个数组tmp1和tmp2存储,这两个数组都是有序序列
//这样的话,从原本的931ms减少到125ms
tmp1[k+]=-;tmp2[k+]=-; //将tmp1和tmp2的第k+1个元素设为-1,即设成较小的值
int a=,b=;
cnt=;
while(cnt<k && (a!=k+||b!=k+)){
if(tmp1[a]>tmp2[b]){
dp[j][++cnt]=tmp1[a];
a++;
}
else{
dp[j][++cnt]=tmp2[b];
b++;
}
if(dp[j][cnt]==dp[j][cnt-])
cnt--;
} } }
printf("%d\n",dp[v][k]);
}
return ;
}