本文共 1347 字，大约阅读时间需要 4 分钟。
题目：
题目大意：
有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一定是按照从大到小的顺序排列的。代码：
#include#include #include #include #include #include #define SQ(x) ((x)*(x))#define MP make_pairconst 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 =p2 || 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;}
转载地址：http://gpzni.baihongyu.com/