01分数规划
程序员文章站
2023-09-07 17:09:32
问题
$01$分数规划是用来解决这样一类问题
>有$n$个物品,每个物品都有一个属性$p$和$w$。要从中选出$K$个物品使得$\frac{\sum\limits_{i=1}^Kp_i}{\sum\limits_{i=1}^Kw_i}$最大,输出最大值。要求是个分数 ......
问题
\(01\)分数规划是用来解决这样一类问题
有\(n\)个物品,每个物品都有一个属性\(p\)和\(w\)。要从中选出\(k\)个物品使得\(\frac{\sum\limits_{i=1}^kp_i}{\sum\limits_{i=1}^kw_i}\)最大,输出最大值。要求是个分数
思想
首先二分一个答案\(x\)。
然后将上面的问题转化为要选\(k\)个物品使得\[\frac{\sum\limits_{i=1}^kp_i}{\sum\limits_{i=1}^kw_i} \geq x\]
即\[\sum\limits_{i=1}^kp_i-\sum\limits_{i=1}^kw_i\times x \ge 0\]
即\[\sum\limits_{i=1}^k{p_i-w_i \times x} \ge 0\]
所以对于每个物品,按照上面这个式子排个序。看最大的k个是否满足条件即可。如果满足条件就统计出答案。
例题
代码
/* * @author: wxyww * @date: 2019-02-09 08:30:09 * @last modified time: 2019-02-09 09:00:36 */ #include<algorithm> #include<cstring> #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> using namespace std; typedef long long ll; const int n = 50000 + 10; const double eps = 1e-9; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } struct node { int w,p; double x; }a[n]; bool tmp(node x,node y) { return x.x > y.x; } int n,k; int check(double w,int &x,int &y) { for(int i = 1;i <= n;++i) a[i].x = double(a[i].w) - double(a[i].p * w); sort(a + 1,a + n + 1,tmp); double ans = 0; for(int i = 1;i <= k;++i) ans += a[i].x; if(ans >= 0) { x = 0,y = 0; for(int i = 1;i <= k;++i) { x += a[i].w; y += a[i].p; } int g = __gcd(x,y); x /= g; y /= g; return 1; } return 0; } int main() { n = read(); k = read(); double r = 0; for(int i = 1;i <= n;++i) a[i].p = read(),a[i].w = read(),r = max(r,(double)a[i].w); double l = 0; int x,y; while(r - l > eps) { double mid = (l + r) / 2; if(check(mid,x,y)) l = mid; else r = mid; } printf("%d/%d\n",x,y); return 0; }
上一篇: PHP的高效率写法
推荐阅读
-
上海大学是个非常变态的大学?上海大学录取分数线2021是多少?
-
多少分能上鲁东大学?曲师和鲁东大学哪个好?附鲁东大学录取分数线2021参考
-
重庆分数线最低的本科大学名单汇总(2021年参考)
-
放弃985去中国人民*大学好不好?附中国人民*大学2020年录取分数线
-
放弃985去西电值吗?附西安电子科技大学排名2021最新排名及录取分数线
-
上海分数线最低的本科大学名单汇总(2021年参考)
-
2021年浙江省15所重点大学排名及录取分数线
-
2021非师范生禁止考教师资格证?附比较好分数低的师范大学名单
-
985211最低分数线是哪所学校?附985211师范大学录取分数线(2021年参考)
-
python实现对求解最长回文子串的动态规划算法