洛谷CF1458B题解：01背包策略解析

"本资源是关于Codeforces (CF) 第1458场竞赛问题B (GlassHalfSpilled) 的详细解题报告，主要使用C++编程语言进行解答。" 在洛谷CF1458B题目中，我们面对的是一个与01背包问题相关的优化问题。题目要求我们考虑一序列的瓶子，每个瓶子有自己的容量`c[i]`和含水量`v[i]`。当选择一瓶时，它可以贡献`b_i`单位的水，如果不选择，则只能贡献`b_i / 2`单位的水。目标是确定一个子集，使得这些瓶子在不超过特定最大容量限制的情况下，能够获得最大的总水量。 解题的关键在于使用动态规划（Dynamic Programming, DP）来解决这个问题。设`dp[i][j]`表示前`i`个瓶子中选择一部分，使得最大容量为`j`时可以获得的最大水量。初始化`dp`数组为一个二维数组，大小为`110 x 10010`，这是因为瓶子的数量可能最多为110个，而容量可能达到10000。 动态规划的状态转移方程可以表示为： ```cpp dp[i][j]=max(dp[i][j], min(double(j), dp[i-1][j-c[x]] + v[x])); ``` 在这个方程中，`x`是当前处理的瓶子的下标。这意味着我们在当前容量`j`下，可以选择不放第`i`个瓶子（保持`dp[i][j]`不变），或者选择它，但要确保不超过总容量（即`j >= c[x]`），此时我们可以通过加入`v[x]`的水量。 在遍历所有瓶子后，我们需要找到第`i`个答案，即在不超出总容量的情况下，从剩余的水中尽可能多地添加水。这个答案可以通过遍历所有可能的容量`j`，并计算`dp[i][j]`加上不超过`((sum - dp[i][j]) / 2)`的剩余水量的最大值来得到。最终输出结果保留一位小数。 完整的C++代码如下： ```cpp #include <bits/stdc++.h> using namespace std; double dp[110][10010]; int c[110], v[110]; int main() { int n; double sum = 0; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d%d", &c[i], &v[i]); sum += v[i]; } for (int i = 0; i <= n; i++) { for (int j = 1; j <= 10000; j++) { dp[i][j] = -1000000000.000000000; } } for (int i = 1; i <= n; i++) { for (int j = i; j >= 1; j--) { for (int k = 10000; k >= c[i]; k--) { dp[j][k] = max(dp[j][k], min(double(k), dp[j - 1][k - c[i]] + v[i])); } } } double ans = 0; for (int j = 0; j <= 10000; j++) { ans = max(ans, dp[n][j] + min(double(n - dp[n][j]), (sum - dp[n][j]) / 2)); } printf("%.1f000000000", ans); return 0; } ``` 这段代码实现了题目要求的算法，通过动态规划求解最大水量，并且在最后给出了保留一位小数的精确答案。