首页 > 代码库 > 【dp】Bone Collector II
【dp】Bone Collector II
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2639
题意： 01背包第k优解， 背包九讲原题。“
对于求次优解、第K优解类的问题，如果相应的最优解问题能写出状态转移方程、用动态规划解决，那么求次优解往往可以相同的复杂度解决，第K优解则比求最优解的复杂度上多一个系数K。
其基本思想是将每个状态都表示成有序队列，将状态转移方程中的max/min转化成有序队列的合并。这里仍然以01背包为例讲解一下。
首先看01背包求最优解的状态转移方程：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
。如果要求第K优解，那么状态f[i][v]就应该是一个大小为K的数组f[i][v][1..K]。其中f[i][v][k]表示前i个物品、背包大小为 v时，第k优解的值。“f[i][v]是一个大小为K的数组”这一句，熟悉C语言的同学可能比较好理解，或者也可以简单地理解为在原来的方程中加了一维。 显然f[i][v][1..K]这K个数是由大到小排列的，所以我们把它认为是一个有序队列。
然后原方程就可以解释为：f[i][v]这个有序队列是由f[i-1][v]和f[i-1][v-c[i]]+w[i]这两个有序队列合并得到的。有序队列f[i-1][v]即f[i-1][v][1..K]，f[i-1][v-c[i]]+w[i]则理解为在f[i-1][v-c[i]] [1..K]的每个数上加上w[i]后得到的有序队列。合并这两个有序队列并将结果的前K项储存到f[i][v][1..K]中的复杂度是O(K)。最后的答案是f[N][V][K]。总的复杂度是O(VNK)。
” ---- 摘自背包九讲
#define _CRT_SECURE_NO_WARNINGS#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#define Zero(x) memset(x, 0, sizeof(x))using namespace std;const int maxn = 1004;int f[32][maxn];int n, V, k;int C[maxn];int W[maxn];int a[32], b[32];int main() { int T; cin >> T; while (T--) { cin >> n >> V >> k; Zero(f); Zero(a); Zero(b); for (int i = 1; i <= n; ++i) { scanf("%d", W + i); } for (int i = 1; i <= n; ++i) { scanf("%d", C + i); } for (int i = 1; i <= n; ++i) { for (int v = V; v >= C[i]; v--) { for (int j = 1; j <= k; ++j) { a[j] = f[j][v]; b[j] = f[j][v - C[i]] + W[i]; } int x, z, y; x = y = z = 1; while (z <= k && (x <= k || y <= k)) { if (a[x] >= b[y]) { f[z][v] = a[x]; x++; } else { f[z][v] = b[y]; y++; } if (f[z - 1][v] != f[z][v]) z++; } } } printf("%d\n", f[k][V]); }}
【dp】Bone Collector II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。