P4377 [USACO18OPEN]Talent Show

àì夳堔傛蜴生んèń 2021-12-22 15:56 148阅读 0赞

这道题可以作为最优比率背包问题的模板题了。好像属于01分数规划。

我们这里用二分答案的方法解决。

题目要我们求\\(\\frac\{\\sum\{t\}\}\{\\sum\{w\}\}\\)的最大值。

我们设答案为\\(ans\\)，则\\(ans \\leq \\frac\{\\sum\{t\}\}\{\\sum\{w\}\}\\)。

化简一下就得到：

\\\[\\sum\{t\} - ans \\times \\sum\{w\} \\geq 0\\\]

注意上面的式子的条件是存在，而不是任意。

显然这个式子越大越难满足，越小越容易满足。所以我们可以二分答案。

现在谈谈如何check：

题目说参加比赛的奶牛总重量必须至少为\\(W\\)，但是\\(w\_i \\leq 10^6\\)，怎么办？

考虑到\\(W \\leq 1000\\)，我们弄个\\(W+1\\)代替大于等于它的所有情况。

所以用01背包的方式去dp，最终去看看\\(dp\[m\]\\)跟\\(dp\[m + 1\]\\)有没有一个满足大于等于0的。如果有就成立。

--------------------

由于自己蔡，在输出的时候又出锅啦。

在最后输出的时候，不要去用floor函数，直接强制类型转换为int即可。暴力下取整。

似乎因为用了这个东西而被卡精度。。。

代码：

#include<bits/stdc++.h> using std::cin; using std::cout; using std::endl; const int maxn = 250, maxm = 1005; const double eps = 1e-5; int n, m; int weight[maxn], value[maxn]; double val[maxn]; double dp[maxm]; bool check(double ans) { for(int i = 1; i <= n; i++) val[i] = value[i] - ans * weight[i]; for(int i = 1; i <= m + 1; i++) dp[i] = -1e18; for(int i = 1; i <= n; i++) { for(int j = m + 1; j >= 0; j--) { dp[std::min(m + 1, j + weight[i])] = std::max(dp[std::min(m + 1, j + weight[i])], dp[j] + val[i]); } } return dp[m] >= eps || dp[m + 1] >= eps; } int main() { cin >> n >> m; double left = 0, right = 0, ans = -1; for(int i = 1; i <= n; i++) { cin >> weight[i] >> value[i]; right += value[i]; } while(right - left > eps) { double mid = (left + right) * 0.5; if(check(mid)) ans = mid, left = mid + eps; else right = mid - eps; } printf("%d", (int)(ans * 1000)); return 0; }

转载于:https://www.cnblogs.com/Garen-Wang/p/10959573.html