POJ 2976 01分数规划基础题目

题意：
      给你一组"数",一共n个，每个数有两个权值，价钱a[i],代价b[i]，让你选择n - k使得 sigma(a[i]) / sigma(b[i]) * 100 最大；


思路：

      毫无疑问这个是01分数规划的最进本形式，唯一的限制就是取个数，那么我们直接sort以下，取出来就行了。没啥解释的，这个是自己的第一个01分数规划，一会要自己总结下01分数规划的理解了，感觉不是很难，就是证明点东西。

自己总结的01分数规划：

http://blog.csdn.net/u013761036/article/details/26666261

#include<stdio.h> #include<algorithm>#define N 1000 + 10 #define INF 1000000000 #define eps 0.000001using namespace std;bool camp(double a ,double b) {return a > b; }double a[N] ,b[N] ,d[N];bool ok(double L ,int n ,int k) {double sum = 0;for(int i = 1 ;i <= n ;i ++)d[i] = a[i] - L * b[i];sort(d + 1 ,d + n + 1 ,camp);for(int i = 1 ;i <= n - k ;i ++)sum += d[i];return sum >= 0; }int main () {int n ,k ,i;while(~scanf("%d %d" ,&n ,&k) && n + k){for(i = 1 ;i <= n ;i ++)scanf("%lf" ,&a[i]);for(i = 1 ;i <= n ;i ++)scanf("%lf" ,&b[i]);double low ,up ,mid ,ans = 0;low = 0 ,up = INF;while(up - low >= eps){mid = (low + up) / 2;if(ok(mid ,n ,k))ans = low = mid;elseup = mid;}ans *= 100;printf("%.0lf\n" ,ans);}return 0; }

总结

以上是生活随笔为你收集整理的POJ 2976 01分数规划基础题目的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。