Error message here!

Hide Error message here!

Error message here!

Hide Error message here!

Error message here!

Close

# [算法xio讲堂#1]01分数规划

chhokmah 2019-02-15 14:53:00 阅读数:255 评论数:0 点赞数:0 收藏数:0

# 定义

01分数规划问题主要包含以下几个问题：

• 一般的01分数规划
• 最优比率生成树
• 最优比率环

# 关于01分数规划的关键

F(L)=sigma(a[i]x[i])-Lsigma(b[i]x[i])
F(L)=sigma(a[i]
x[i]-Lb[i]a[i])
F(L)=sigma((a[i]-Lb[i])x[i])

F(L)=sigma(d[i]*x[i])

# 关于为什么01分数规划不能用贪心？

（个人看法）

## 一、01分数规划算法

$R= \frac{\sum_{i=1}^{n}{a[i]*x[i]}}{\sum_{i=1}^{n}{b[i]*x[i]}}$

## 二、贪心算法

$xi=\frac {valuei}{weighti}$

$R=\sum{xi}$

# 例题

## Description

In a certain course, you take n tests. If you get ai out of bi questions correct on test i, your cumulative average is defined to be

$100*\frac{\sum_{i=1}^{n}{ai}}{\sum_{i=1}^{n}{ai}}$

Given your test scores and a positive integer k, determine how high you can make your cumulative average if you are allowed to drop any k of your test scores.

Suppose you take 3 tests with scores of 5/5, 0/1, and 2/6. Without dropping any tests, your cumulative average is . However, if you drop the third test, your cumulative average becomes .
Input

• The input test file will contain multiple test cases, each containing exactly three lines. The first line contains two integers, 1 ≤ n ≤ 1000 and 0 ≤ k < n. The second line contains n integers indicating ai for all i. The third line contains n positive integers indicating bi for all i. It is guaranteed that 0 ≤ ai ≤ bi ≤ 1, 000, 000, 000. The end-of-file is marked by a test case with n = k = 0 and should not be processed.
Output
• For each test case, write a single line with the highest cumulative average possible after dropping k of the given test scores. The average should be rounded to the nearest integer.
Sample Input

3 1
5 0 2
5 1 6
4 2
1 2 7 9
5 6 7 9
0 0
Sample Output

• 83
100
Analysis

• 01分数规划的入门题，我们就认真讲解一下。
首先我们要理解题目的意思，大意是：给你一个价值a[i]和代价b[i]，然后我们选举n-k个物品，使得总价值/总代价。
理解了题目后，我们就是要用到了今天学习的01分数规划。
$R=\frac{\sum{ai*xi}}{\sum{bi*xi}}$
我们把这个算式进行一个变形：
$F(l)=\sum{ai*xi}-l*\sum{bi*xi}$
上文已经分析过如何进行移项便是以下的算式：
$F(l)=\sum{(ai-l*bi)*xi}$
根据这个算式，因为a[i]和b[i]是已知的，所以我们就把$ai-lbi$$这个算式定义成$$ di$
所以原来的又长又臭的算式就可以成为$F(l)=\sum di xi$
这样我们的算式中只有$$l$$是未知的，我们只需要用二分来枚举$$l$$在算出$$F(l)$$就可以了。

## Code

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cctype>
#include <cmath>
#include <time.h>
#include <map>
#include <set>
#include <vector>
using namespace std;
#define ms(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const double eps=1e-7;
int n,k;
double a[1010],b[1010],d[1010];
{
int X=0,w=0; char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}
int main()
{
while (1)
{
if (n==0 && k==0) break;
for (int i=1;i<=n;i++) scanf("%lf",&a[i]);
for (int i=1;i<=n;i++) scanf("%lf",&b[i]);
double l=0.0,r=1.0,mid;
while (r-l>eps)
{
mid=(l+r)/2;
for (int i=1;i<=n;i++) d[i]=a[i]-mid*b[i];
sort(d+1,d+1+n);
double sum=0.0;
for (int i=k+1;i<=n;i++) sum+=d[i];
if (sum>0) l=mid;
else r=mid;
}
printf("%.0f\n",mid*100);
}
return 0;
}

## Description

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
• 输出单位体积的价值（用约分后的分数表示）。
Sample Input

3 2
2 2
5 3
2 1
Sample Output

• 3/4
Analysis

• 入门题，我们算出答案后，一个gcd就好了。
Code
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cctype>
#include <cmath>
#include <time.h>
#include <map>
#include <set>
#include <vector>
using namespace std;
#define ms(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int maxn = 50005;
const double eps = 1e-9;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
struct node
{
int w,p;
double val;
bool operator < (const node& T) const{
return val>T.val;
}
}b[maxn];
double mid;
ll anss,ansx,tmps,tmpx;
int n,k;
bool check()
{
int tot=0;
for(int i=0;i<n;i++)b[i].val = 1.0*b[i].p-b[i].w*mid;
sort(b,b+n);
double sum=0;
tmps=0,tmpx=0;
for(int i=0;i<k;i++)sum+=b[i].val,tmps+=b[i].p,tmpx+=b[i].w;
if(sum-0>=eps)return true;
return false;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) scanf("%d%d",&b[i].w,&b[i].p);
double l=0,r=500000;
for(int i=0;i<100;i++)
{
mid=(l+r)/2;
if(check())l=mid,anss=tmps,ansx=tmpx;
else r=mid;
}
ll tmp=gcd(anss,ansx);
anss/=tmp,ansx/=tmp;
printf("%lld/%lld\n",anss,ansx);
return 0;
}

## Description

David the Great has just become the king of a desert country. To win the respect of his people, he decided to build channels all over his country to bring water to every village. Villages which are connected to his capital village will be watered. As the dominate ruler and the symbol of wisdom in the country, he needs to build the channels in a most elegant way.

After days of study, he finally figured his plan out. He wanted the average cost of each mile of the channels to be minimized. In other words, the ratio of the overall cost of the channels to the total length must be minimized. He just needs to build the necessary channels to bring water to all the villages, which means there will be only one way to connect each village to the capital.

His engineers surveyed the country and recorded the position and altitude of each village. All the channels must go straight between two villages and be built horizontally. Since every two villages are at different altitudes, they concluded that each channel between two villages needed a vertical water lifter, which can lift water up or let water flow down. The length of the channel is the horizontal distance between the two villages. The cost of the channel is the height of the lifter. You should notice that each village is at a different altitude, and different channels can't share a lifter. Channels can intersect safely and no three villages are on the same line.

As King David's prime scientist and programmer, you are asked to find out the best solution to build the channels.
Input

• There are several test cases. Each test case starts with a line containing a number N (2 <= N <= 1000), which is the number of villages. Each of the following N lines contains three integers, x, y and z (0 <= x, y < 10000, 0 <= z < 10000000). (x, y) is the position of the village and z is the altitude. The first village is the capital. A test case with N = 0 ends the input, and should not be processed.
Output
• For each test case, output one line containing a decimal number, which is the minimum ratio of overall cost of the channels to the total length. This number should be rounded three digits after the decimal point.
Sample Input

4
0 0 0
0 1 1
1 1 2
1 0 3
0
Sample Output

• 1.000
Analysis

• 大意：给定一张图，每条边有一个收益值和一个花费值， 求一个生成树，要求花费/收益最小，输出这个值
分析：现在的限制就有点复杂了，要求解必须是一棵生成 树。而且这道题目要求的花费/收益最小，当然你求收益/ 花费最大然后反过来也是可以的，注意处理花费为0的情 况。如果求最小的，处理方法是也类似的，先求个D，然 后做一次最小生成树，显然得到的就是函数值。
Code

## Description

Farmer John has decided to reward his cows for their hard work by taking them on a tour of the big city! The cows must decide how best to spend their free time.

Fortunately, they have a detailed city map showing the L (2 ≤ L ≤ 1000) major landmarks (conveniently numbered 1.. L) and the P (2 ≤ P ≤ 5000) unidirectional cow paths that join them. Farmer John will drive the cows to a starting landmark of their choice, from which they will walk along the cow paths to a series of other landmarks, ending back at their starting landmark where Farmer John will pick them up and take them back to the farm. Because space in the city is at a premium, the cow paths are very narrow and so travel along each cow path is only allowed in one fixed direction.

While the cows may spend as much time as they like in the city, they do tend to get bored easily. Visiting each new landmark is fun, but walking between them takes time. The cows know the exact fun values Fi (1 ≤ Fi ≤ 1000) for each landmark i.

The cows also know about the cowpaths. Cowpath i connects landmark L1i to L2i (in the direction L1i -> L2i ) and requires time Ti (1 ≤ Ti ≤ 1000) to traverse.

In order to have the best possible day off, the cows want to maximize the average fun value per unit time of their trip. Of course, the landmarks are only fun the first time they are visited; the cows may pass through the landmark more than once, but they do not perceive its fun value again. Furthermore, Farmer John is making the cows visit at least two landmarks, so that they get some exercise during their day off.

Help the cows find the maximum fun value per unit time that they can achieve.
Input

• Line 1: Two space-separated integers: L and P
• Lines 2..L+1: Line i+1 contains a single one integer: Fi
• Lines L+2..L+P+1: Line L+i+1 describes cow path i with three space-separated integers: L1i , L2i , and Ti
Output
• Line 1: A single number given to two decimal places (do not perform explicit rounding), the maximum possible average fun per unit time, or 0 if the cows cannot plan any trip at all in accordance with the above rules.
Sample Input

5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2
Sample Output

• 6.00
Analysis

• 大意：给定一张图，边上有花费，点上有收益，点可以多 次经过，但是收益不叠加，边也可以多次经过，但是费用 叠加。求一个环使得收益和/花费和最大，输出这个比值。
分析：比上面更加的恶心了。先不说环的问题，就是花费 和收益不在一处也令人蛋疼。这时候需要用到几个转化和 结论。
首先的一个结论就是，不会存在环套环的问题，即最优的方 案一定是一个单独的环，而不是大环套着小环的形式。这个的 证明其实非常的简单，大家可以自己想一下（提示，将大环上 的收益和记为x1,花费为y1，小环上的为x2,y2。重叠部分的花 费为S。表示出来分类讨论即可）。有了这个结论，我们就可以 将花费和收益都转移到边上来了，因为答案最终一定是一个环， 所以我们将每一条边的收益规定为其终点的收益，这样一个环 上所有的花费和收益都能够被正确的统计。
解决了蛋疼的问题之后，就是01分数规划的部分了，我们只 需要计算出D数组后找找有没有正权环即可，不过这样不太好， 不是我们熟悉的问题，将D数组全部取反之后，问题转换为查找 有没有负权环，用spfa或是bellman_ford都可以。

## Code

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N 100010
using namespace std;
const double eps=1e-5;
struct edge
{
int v,nxt,w;
double c;
} e[N<<1];
bool vis[N];
double dis[N];
int n,m,mct,u,v,w;
{
int x=0,f=1;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
{
}
bool spfa(int u)
{
vis[u]=1;
{
int v=e[i].v;
if(dis[v]>dis[u]+e[i].c)
{
dis[v]=dis[u]+e[i].c;
if(vis[v] || spfa(v))
{
vis[v]=0;
return 1;
}
}
}vis[u]=0;return 0;
}
void judge(double r)
{
for(int i=1; i<=mct; i++)
e[i].c=(double)e[i].w*r-f[e[i].v];
return;
}
bool check()
{
for(int i=1; i<=n; i++)
if(spfa(i))return 1;
return 0;
}
int main()
{
for(int i=1; i<=m; i++)
{
}
double l=0,r=100000,ans;
while(r-l>eps)
{
double mid=(l+r)/2;
judge(mid);
if(check())
{
ans=mid;l=mid;
}
else r=mid;
}
printf("%.2f\n",ans);
return 0;
}

https://www.cnblogs.com/chhokmah/p/10356777.html