python

10 KiB

Raw Permalink Blame History Unescape Escape

This file contains invisible Unicode characters that may be processed differently from what appears below. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to reveal hidden characters.

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

`01`分数规划

【挖坑待填】

水平所限，01分数规划刚刚入门，还是由SPFA求负环的题引入的01分数规划，还是完成了入门篇之后，回到学习主线，继续学习SPFA+负环的图论章节，待知识体系完善后，三刷再来攻克其它相关试题。黄海　于2022-11-10 17:04

一、定义

01分数规划问题：所谓的01分数规划问题就是指这样的一类问题，给定两个数组，a[i]表示选取i的收益，b[i]表示选取i的代价。如果选取i，定义w[i]=1否则w[i]=0。每一个物品只有选或者不选两种方案，求一个选择方案使得

\large \displaystyle R=\frac{\sum (a[i] \times w[i])}{\sum (b[i]\times w[i])}

取得最值，即所有选择物品的总收益/总代价的值最大或是最小

01分数规划问题主要包含一般的01分数规划、最优比率生成树问题、最优比率环问题、最大密度子图等。我们将会对这四个问题进行讨论。 永远要记得，我们的目标是使R取到最值。这句话我会在文中反复的强调

二、为啥不能直接按性价比排序，从大到小找出指定个数不就行了吗？

如果真要这么干，那是贪心的作法，这样做是不对的，原因：举个反例：

\LARGE \frac{3}{1} ~~~~ \frac{80}{40}(\frac{2\times 40}{1\times 40}) ~~~~ \frac{1.9}{1}

k=2,就是需要选择出两组来，保证选择的性价比值最高。

形象化理解一下：

① \large \displaystyle \frac{3}{1},表示价值3,重量1
② \large \displaystyle \frac{80}{40},表示价值80,重量40
③ \large \displaystyle \frac{1.9}{1},表示价值1.9,重量1

按单个性价比排序，应该是 \large ①>②>③，按贪心思想，应该选择\large ①,②

而如果按上面加和，除以，下面加和的话就是：

\displaystyle①+②=\frac{3+80}{1+40}=2.024

\displaystyle ①+③=\frac{3+1.9}{1+1}=2.45 很明显\large ①+③>①+②

应该选择 \large ①+③这个组合!

总结：上来就除，除完再排名，和，上面加和除以下面加和不是一回事，要想清楚！

三、分析过程

数学分析中一个 很重要的方法 就是 分析目标式，来看目标式:

\large \displaystyle R =\frac{\sum (a[i]\times w[i])}{\sum(b[i]\times w[i])}

分析一下它有什么性质:

我们先定义一个函数

\large F(L):=\sum(a[i]\times w[i])-L\times \sum(b[i]\times w[i])

显然这只是对目标式的一个简单的变形。

分离参数，得到

\large F(L):= w[i] \times \sum(a[i]-L\times b[i])

这时我们就会发现，如果L已知的话，\large a[i]-L\times b[i]就是已知的，当然w[i]是未知的 。记

\large d[i]=a[i]-L\times b[i]

那么

\large F(L):=w[i]\times \sum(d[i]*x[i])

多么简洁的式子,我们就对这些东西下手了。

再次提醒一下，我们的目标是使R取到最大值

我们来分析一下这个函数，它与目标式的关系非常的密切，L就是目标式中的R，最大化R也就是最大化L。

F的值是由两个变量共同决定的，即方案X和参数L。对于一个确定的参数L来说，方案的不同会导致对应的F值的不同，那么这些东西对我们有什么用呢?

假设我们已知存在一个方案X使得F(L)>0，这能够证明什么?

\large F(L):=\sum (a[i]\times w[i])-L\times \sum (b[i]\times w[i])>0

即

\large \frac{\sum(a[i]\times w[i])}{\sum(b[i]\times w[i])} >L

也就是说，如果一个方案使得F(L)>0说明了这组方案可以得到一个比现在的L更优的一个L'，既然有一个更优的解，那么为什么不用呢？

显然，d数组是随着L的增大而单调减的。也就是说，存在一个临界的L使得不存在一种方案，能够使F(L)>0. 我们猜想，这个时候的L就是我们要求的 最优解。之后更大的L值则会造成无论任何一种方案，都会使F(L)<0.类似于上面的那个变形，我们知道，F(L)<0是没有意义的，因为这时候的L是不能够被取得的。当F(L)=0使，对应方案的R值恰好等于此时的L值。

综上，函数F(L)有这样的一个性质：在前一段L中可以找到一组对应的X使得F(L)>0，这就提供了一种证据，即有一个比现在的L更优的解，而在某个L值，存在一组解使得F(L)=0,且其他的F(L)<0，这时的L无法继续增大，即这个L就是我们期望的最优解，之后的L会使得无论哪种方案都会造成F(L)<0.而我们已经知道，F(L)<0是没有任何意义的，因为此时的L值根本取不到。

最后一次提醒，我们的目标是R！！！

如果现在你觉得有些晕的话，那么我要提醒你的就是，千万不要把F值同R值混淆。F值是根据我们的变形式求的d数组来计算的，而R值则是我们所需要的真实值，他的计算是有目标式决定的。F值只是提供了一个证据，告诉我们真正最优的R值在哪里，他与R值本身并没有什么必然的联系。

根据这样的一段性质，很自然的就可以想到二分L值，然后验证是否存在一组解使得F(L)>0，有就移动下界，没有就移动上界。

所有的01分数规划都可以这么做，唯一的区别就在于求解时的不同——因为每一道题的限制条件不同，并不是每一个解都是可行解的。比如在普通的数组中，你可以选取1、2、3号元素，但在生成树问题中，假设1、2、3号元素恰好构成了一个环，那就不能够同时选择了，这就是需要具体问题，具体分析的部分。

二分是一个非常通用的办法，但是我们来考虑这样的一个问题，二分的时候我们只是用到了F(L)>0这个条件，而对于使得F(L)>0的这组解所求到的R值没有使用。因为F(L)>0,我们已经知道了R是一个更优的解，与其漫无目的的二分，为什么不将解移动到R上去呢？求01分数规划的另一个方法就是Dinkelbach算法，他就是基于这样的一个思想，他并不会去二分答案，而是先随便给定一个答案，然后根据更优的解不断移动答案，逼近最优解。由于他对每次判定使用的更加充分，所以它比二分会快上很多。但是，他的弊端就是需要保存这个解，而我们知道，有时候验证一个解和求得一个解的复杂度是不同的。二分和Dinkelbach算法写法都非常简单，各有长处，大家要根据题目谨慎使用。

五、实践

上面啰嗦了这么多，现在给出程序的框架。

二分法

L = 1 ; R = INF;
while( R - L > Eps)
  Mid:=(L+R)/2;
  For I=1..X do D[i]:=A[i]-Mid*B[i];//根据Mid计算D数组
  if check(Mid) 
    L:=Mid;
  else 
    R:=Mid；

`Dinkelbach`算法

L:=随便什么东西;
Repeat
  Ans:=L;
  For I=1..X do D[i]:=A[i]-L*B[i];//根据L计算D数组
  检查解并记录;
  p:=0;q:=0;
  for I=每一个元素 do 
    如果元素I在解中
      begin
        p:=p+A[i];q:=q+B[i];
      end;
  L:=p/q;//更新解
Until abs(Ans-L)<Eps;

其中检查解的部分是要看具体情况的。

三、常见模型

1、`01`规划

裸01规划例题：POJ2976 Dropping tests

大意：给定A数组B数组，让求删除k个数后,即保留(选择) N-K个使得R最大，输出Round(100*R)

分析：限制很简单，只是数目上有所限制，处理方法也很简单，求出D数组后从大到小排列，从前向后取N-K个即可，这时的D一定是最大的。

另外：如果是最小选择N-K个怎么办？

办法是一样的，从大到小排列序，傻子才多选，能少选就少选。反正F值具体的大小没什么关系，我们只要知道他与0的关系即可。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 1010;
const int INF = 0x3f3f3f3f;
int n, k;
int a[N], b[N];
const double eps = 1e-8;

double d[N];

bool check(double x) {
    for (int i = 0; i < n; i++) d[i] = a[i] - x * b[i];
    sort(d, d + n, greater<double>()); //由大到小排序

    double sum = 0;
    for (int i = 0; i < n - k; i++) sum += d[i];
    return sum >= 0; //从大到小选n-k个，看ans是否为可行的解
}

int main() {
    while (cin >> n >> k && (n || k)) {
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) cin >> b[i];

        //浮点数二分
        double l = 0, r = INF;
        while (r - l > eps) {
            double mid = (l + r) / 2; //注意浮点数不能用右移操作
            if (check(mid))
                l = mid; //向右逼近，使结果更大一些
            else
                r = mid; //向左逼近，使结果更小一些
        }
        printf("%.0lf\n", l * 100); // 四舍五入
    }
    return 0;
}

2、`01`规划与最小生成树

最优比率生成树例题：POJ2728 Desert King

3、01规划与环

最优比率生成环例题：P1768 天路 Acwing 361 观光奶牛

4、`01`规划与网络流

最优比率最小割 例题：Acwing 2279 网络战争题解：网络战争

[POJ2728]Desert King [POJ3621]Sightseeing Cows

10 KiB Raw Permalink Blame History Unescape Escape

01分数规划