5 Bone Collector II 题解

题面

传送门

N个物品，背包容量为V，每个物品有相应的体积w和价值v。求严格第k优解（背包容量为V的情况下，价值第k多的方案）

N\leq 100 ,\,V\leq 1000,\,k\leq 30

题解

思路

求第k优解，我们可以先想想次优解如何求解。

我们可以类比次短路，我们定义dis[x][0]与dis[x][1]分别表示由s到x的最短路和次短路，在进行最短路更新时，顺便将次短路更新。
那么背包次优解不也是一样的道理吗，我们可以定义f[x][0]与f[x][1]分别表示容量为x的情况下的最优解与次优解。

类比次优解，我们不难想到k优解的解法，我们在原有的f[]的基础上加一维。
f[i][j]表示在容量限制为i的情况下的第j优解。

这样我们处理好了如何表示第k优解，那么如何进行快速的转移呢？
如果我们暴力的将当前状态与上一状态的情况进行排序，取前k个，那么时间复杂度就是O(N\,V\,k\,logk)。

并且这种方法有个弊端，就是我们无法准确得知我们要分别在两个数组中取多少个元素放置在待排序数组中。当然，在真正实现的时候我们可以求出x*k优解，然后在两个数组中取远大于k个元素放入待排序数组中，出错概率也不大。当然，我们可以优化。

我们可以利用这两个数组的性质进行优化。
因为两个数组分别对应着两个状态的有序递减的解，那么我们可以利用这个性质，用类似归并排序的方法，求到1\sim k优解，单次时间复杂度为O(k)。

这样，这道题就写完了

code

typedef long long ll;
const int N = 1e3 + 10;

int t, n, m, k;
int v[N], w[N];
ll f[N][110], b[N];

int main() {
	scanf("%d", &t);
	while(t--) {
		memset(f, 0, sizeof f);
		scanf("%d%d%d", &n, &m, &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 = m; j >= w[i]; j--) {
				int cnt = 0;
				int p1 = 1, p2 = 1;
				//这里因为是严格k优解，所以多算一点
				while(p1 <= 50 && p2 <= 50) {
					if(f[j][p1] > f[j - w[i]][p2] + v[i]) {
						b[++cnt] = f[j][p1];
						p1++;
					} else {
						b[++cnt] = f[j - w[i]][p2] + v[i];
						p2++;
					}
				}
				for(int c = p1; c <= 50; c++) {
					b[++cnt] = f[j][c];
				}
				for(int c = p2; c <= 50; c++) {
					b[++cnt] = f[j - w[i]][c] + v[i];
				}
				for(int c = 1, cc = 0; c <= 100; c++) {
					if(b[c] == b[c - 1]) continue;
					f[j][++cc] = b[c];
					if(cc == k) break;
				}
			}
		}
		
		printf("%lld\n", f[m][k]);
	}
	return 0;
}