背包专项训练

bottle

题意简述

link
有 \(n\) 瓶水，第 \(i\) 瓶水有剩余水量 \(a_i\) 和最大容积 \(b_i\)，在不超过瓶子容积的前提下，小 A 可以把任意多的水从一个瓶子倒向另一个瓶子，所花费的时间等同于倒过去的水的体积。

求最多能得到多少个空瓶，以及在得到最多的空瓶的前提下，他最少需要花费的时间。

对于 \(70\%\) 的数据，\(1 \le n, a_i, b_i \le 100\)。

对于 \(100\%\) 的数据，\(1 \le n, a_i, b_i \le 500\)。

简要分析

题意简化为：选出若干个瓶子，使得选出的瓶子最多，且 总水量 \(\le\) 未被选中的瓶子的总容积，同时要求选中的瓶子的 原有 水量最少。

记 \(\sum a_i\) 为被选为空瓶的总水量，\(\sum a_j\) 为剩余瓶子的总水量，不难得到 \(\sum a_i + \sum a_j = \sum a\)，对 \(b\) 同样如此定义。

题意即可形式化为：使 \(\sum a_i\) 最小，同时保证 \(\sum b_j \ge \sum a\)。

70 pts

对于 \(70\%\) 的数据，\(1 \le n, a_i, b_i \le 100\)。数据范围启发做法，可尝试 \(\mathcal{O}(n^4)\) 的算法。

首先考虑求出最多空瓶数，贪心做法。容积小的瓶子优先选择。因为要满足 \(\sum b_j \ge \sum a\)，显然贪心为真。

然后考虑第二个答案。记 \(f_{i, j}\) 表示用掉 \(i\) 个瓶子 浪费 了容积 \(j\) 所需的最小 \(\sum a_i\)。转移 \(f_{i, j} = \min_{k \in [i, n]}{f_{i - 1, j - b_k} + a_k}\)。

由于要枚举当前走到的位置（\(\mathcal{O}(n)\)），内层枚举用掉的瓶子数（\(\mathcal{O}(n)\)），接着枚举浪费的容积（\(\mathcal{O}(n^2)\)），因此复杂度为 \(\mathcal{O}(n^4)\)。

100 pts

记 \(f_i\) 表示

#include<bits/stdc++.h>
#define N 505
#define M 250005
using namespace std;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) {x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
	return x * f;
}
int n, sum, a[N], b[N], f[M], g[M];
int main(){
	n = read();
	for(int i = 1; i <= n; i++) a[i] = read(), sum += a[i];
	for(int i = 1; i <= n; i++) b[i] = read();
	memset(g, 0x3f, sizeof g);
	int Max = 250000; g[0] = 0;
	for(int i = 1; i <= n; i++){
		for(int k = Max; k >= b[i]; k--){
			if(g[k - b[i]] + 1 < g[k])
			  f[k] = f[k - b[i]] + a[i],
			  g[k] = g[k - b[i]] + 1;
			else if(g[k - b[i]] + 1 == g[k])
			  f[k] = max(f[k], f[k - b[i]] + a[i]);
		}
	}
	int ans1 = INT_MAX, ans2 = -INT_MAX;
	for(int i = sum; i <= Max; i++){
		if(g[i] < ans1) ans1 = g[i], ans2 = f[i];
		else if(g[i] == ans1) ans2 = max(ans2, f[i]);
	}
	printf("%d %d\n", n - ans1, sum - ans2);
	return 0;
}

file

link
小 A 有 \(