[关闭]
@RabbitHu 2017-08-17T08:26:02.000000Z 字数 1642 阅读 1340

背包问题V3 | 分数规划

题解


题目描述

N个物品的体积为W1,W2......Wn(Wi为整数),与之相对应的价值为P1,P2......Pn(Pi为整数),从中选出K件物品(K <= N),使得单位体积的价值最大。

Input
第1行:包括2个数N, K(1 <= K <= N <= 50000)
第2 - N + 1行:每行2个数Wi, Pi(1 <= Wi, Pi <= 50000)

Output
输出单位体积的价值(用约分后的分数表示)。


题解

分数规划!

是布尔类型,表示号物品被选,反之表示不选。

为单位体积的价值:

我们要求 的极值。

我们二分答案 ,对于每个,定义一个函数:

化简一下:

为了方便起见,设:

则:

接下来考虑与0的关系。根据,可以得到:

  1. ,则至少有一组解得到的答案比A优,则A猜小了,应当增加。
  2. ,则不存在任何一组解和A一样优或比A优,则A猜大了,应当减小。

那么我们用来做判断,进行二分即可。

一个注意事项中的解x,是能使最大的解,则应当按照d[i]将每个物品由大到小排序,选择前k个即可。

最后题目要求输出分数怎么办呢?

还是按照“注意事项”里的,把每个物品按照d[i]排序,选择前k个即可。


代码

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. const int N = 50005;
  8. int n, k, a[N], b[N], id[N], up, down;
  9. double d[N];
  10. bool f(double l){
  11. double ret = 0;
  12. for(int i = 1; i <= n; i++)
  13. d[i] = a[i] - l*b[i];
  14. sort(d + 1, d + n + 1);
  15. for(int i = n; i > n - k; i--)
  16. ret += d[i];
  17. return ret >= 0;
  18. }
  19. bool cmp(int x, int y){
  20. return d[x] > d[y];
  21. }
  22. int gcd(int x, int y){
  23. return y ? gcd(y, x % y) : x;
  24. }
  25. int main(){
  26. scanf("%d%d", &n, &k);
  27. for(int i = 1; i <= n; i++)
  28. scanf("%d%d", &b[i], &a[i]);
  29. double l = 0.0, r = 50000.0;
  30. for(int I = 1; I < 100; I++){
  31. double mid = (l + r) / 2;
  32. if(f(mid)) l = mid;
  33. else r = mid;
  34. }
  35. for(int i = 1; i <= n; i++)
  36. d[i] = a[i] - l*b[i];
  37. for(int i = 1; i <= n; i++)
  38. id[i] = i;
  39. sort(id + 1, id + n + 1, cmp);
  40. for(int i = 1; i <= k; i++)
  41. up += a[id[i]], down += b[id[i]];
  42. int g = gcd(up, down);
  43. up /= g, down /= g;
  44. printf("%d/%d\n", up, down);
  45. return 0;
  46. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注