A7 分数规划 • EH's Blog

题目情境#

用途：求分数的最值。

问题：每种物品有两个权值 $a_i$ 和 $b_i$ ，选出若干个物品使得 $\dfrac{\sum a_i}{\sum b_i}$ 最大/最小。

等价：给出 $a_i$ 和 $b_i$ ，求一组 $w_i \in \{0,1\}$ ，最大化或最小化 $\dfrac{\sum w_i \cdot a_i}{\sum w_i \cdot b_i}$ 。

若干个物品：满足给定约束条件的物品。

算法解析#

最大化：二分一个答案 $x$ ，

\frac{\sum w_i \cdot a_i}{\sum w_i \cdot b_i} \ge x

\sum w_i \cdot a_i - x\sum w_i \cdot b_i \ge 0

\sum w_i \cdot (a_i - xb_i) \ge 0

如果和式 $\ge 0$ ，说明 $x$ 是可行的，否则不可行。

最小化：二分一个答案 $x$ ，

\frac{\sum w_i \cdot a_i}{\sum w_i \cdot b_i} \le x

\sum w_i \cdot (a_i - xb_i) \le 0

如果和式 $\le 0$ ，说明 $x$ 是可行的，否则不可行。

Python代码实现#


def check(x):
    s = 0
    for i in range(1, n + 1):
        c[i] = a[i] - x * b[i]
    c[1:n+1] = sorted(c[1:n+1])
    for i in range(k + 1, n + 1):
        s += c[i]
    return s >= 0
def find():
    l = 0
    r = 1
    while r - l > 1e-4:
        mid = (l + r) / 2
        if check(mid):
            l = mid
        else:
            r = mid
    return l


while 1:
    n, k = map(int, input().split())
    if n == 0 and k == 0:
        break
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    a.insert(0, 0)
    b.insert(0, 0)
    c = [0] * (n + 1)
    print("{0:.0f}".format(100 * find()))

python

C++代码实现#

//分数规划+二分+排序 复杂度：nlogn*log(1e4)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=1010;
int n,k;
double a[N], b[N], c[N];

bool check(double x){
  double s=0;
  for(int i=1;i<=n;++i)c[i]=a[i]-x*b[i];
  sort(c+1, c+n+1);
  for(int i=k+1;i<=n;++i) s+=c[i];
  return s>=0;
}
double find(){
  double l=0, r=1;
  while(r-l>1e-4){
    double mid=(l+r)/2;
    if(check(mid)) l=mid;//最大化
    else r=mid;
  }
  return l;
}
int main(){
  while(scanf("%d%d",&n,&k),n){
    for(int i=1;i<=n;i++)scanf("%lf",&a[i]);
    for(int i=1;i<=n;i++)scanf("%lf",&b[i]);
    printf("%.0lf\n", 100*find());
  }
  return 0;
}