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;
}