本文共 1190 字，大约阅读时间需要 3 分钟。
给v大的背包，n个物品的价值和体积，求能装下的第k大的价值是多少。
01背包，第k大。
dp数组多开一维记录从第一大到第k大的值。
内循环用两个数组记录使用当前物品和不使用当前物品的情况。
结束后将两个数组合并到dp数组中。
#include #include #include #include #include #include #include using namespace std;typedef long long LL;const int MAXN = 1e2 + 10;const int MAXV = 1e3 + 10;const int MAXK = 30 + 5;int dp[MAXV][MAXK];int a[MAXN];int b[MAXN];int A[MAXK];int B[MAXK];int main(){ int t; int n, v, k; scanf("%d", &t); while (t--) { memset(dp, 0, sizeof(dp)); scanf("%d%d%d", &n, &v, &k); for (int i = 1;i <= n;i++) scanf("%d", &a[i]); for (int i = 1;i <= n;i++) scanf("%d", &b[i]); for (int i = 1;i <= n;i++) for (int j = v;j >= b[i];j--) { for (int x = 1;x <= k;x++) { A[x] = dp[j - b[i]][x] + a[i]; B[x] = dp[j][x]; } A[k + 1] = -1; B[k + 1] = -1; int x, y, z; x = y = z = 1; //对得到的所有价值排序入队 while (x <= k && (A[y] != -1 || B[z] != -1)) { if (A[y] > B[z]) dp[j][x] = A[y++]; else dp[j][x] = B[z++]; if (dp[j][x] != dp[j][x - 1]) x++; } } printf("%d\n", dp[v][k]); } return 0;}
转载于:https://www.cnblogs.com/YDDDD/p/10464538.html