【POJ】2728 Desert King 最优比率生成树——01分数规划【经典】

2024-09-05 15:38

本文主要是介绍【POJ】2728 Desert King 最优比率生成树——01分数规划【经典】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

最近在刷巨巨们放出来的专题,然后没做几题就卡住了,果然还是太弱了T U T...

这次做到了一题01分数规划求解的生成树问题。

题目大意是这样的:给你一个无向完全图,每条边i都有两个权值,长度a[ i ],花费b[ i ],需要选出其中的一些边构造一颗生成树,生成树需要满足条件:∑ b [ i ] / ∑ a [ i ]最小。

这样我还是先来介绍一下01分数规划吧~


给定一个上述的问题,我们可以设R = ∑x[ i ] * b[ i ] / ∑x[ i ] * a[ i ],其中x[ i ]为0或1表示边i取或者不取。

这里我们先假设对于所有的可行解x[ i ],a[ i ] * x[ i ]都是正数。

我们需要求R的最小值,那么不妨先设一个子问题Q(L) = ∑x[ i ] * b[ i ] - L * ∑x[ i ] * a[ i ] 的最小值,然后我们需要求满足条件(即它是一棵生成树)的L的最小值。

易知L就是R,所以问题等价于求R的最小值

首先我们先对Q(L)移项得:Q(L) = ∑x[ i ] * ( b[ i ] - R * a[ i ] )。

如果我们已知L,那么b[ i ] - L * a[ i ]也是已知的,所以子问题只和两个参数L,x[ i ]有关。并且对于一个L,x[ i ]的选取不同,将可能会导致Q(L)的取值不同。

现在我们假设Q(L) < 0 ,那么我们能得到什么信息?

根据Q(L) = ∑x[ i ] * ( b[ i ] - L * a[ i ] ) < 0 可以推出∑x[ i ] * b[ i ] / ∑x[ i ] * a[ i ] < L ,那么就说明我们找到了一个比R更优的解!为什么不选择更优一点的解呢~

如果Q(L) < 0,那么这时候比L小的解都是不是最优的,自然不需要了。(其实应该理解为它们都是意义的)

当然如果Q(L) = 0,那么我们找到了一个可行解R=L,但是不是最优解,暂时我们还不知道。

如果函数Q(L)满足单调性,则说明如果存在Q(L) = 0,则有且只有这一个解,并且这个解就是我们需要的答案。

证明:

假设L2 > L1,令X[ i ]是L2的一组解向量,Y[ i ]是L1的一组解向量。

那么Q(L2) = ∑X[ i ] * b[ i ] - L2 * ∑X[ i ] * a[ i ] , Q(L1) =∑Y[ i ] * b[ i ] - L1 * ∑Y[ i ] * a[ i ]。

易知∑Y[ i ] * b[ i ] - L2 * ∑Y[ i ] * a[ i ] >= ∑X[ i ] * b[ i ] - L2 * ∑X[ i ] * a[ i ](因为X[ i ],Y[ i ]分别是Q(L2),Q(L1)最小值对应的解向量,所以Y[ i ]放到L2中去一定不会比最小值还小。

所以有:Q(L2) - Q(L1) = ( ∑X[ i ] * b[ i ] - L2 * ∑X[ i ] * a[ i ] ) -( ∑Y[ i ] * b[ i ] - L1 * ∑Y[ i ] * a[ i ] ) <=

                                           ( ∑Y[ i ] * b[ i ] - L2 * ∑Y[ i ] * a[ i ] ) - ( ∑Y[ i ] * b[ i ] - L1 * ∑Y[ i ] * a[ i ] ) =

                                            ( L1 - L2 ) * ∑Y[ i ] * a[ i ] < 0 ( Y[ i ] > 0,a[ i ] > 0 )

因此我们得到了对于L2 > L1,Q(L2) < Q(L1),所以函数Q(L)单调递减。

所以根据Q(L)的单调性,我们很容易知道当Q(L) = 0的时候,R = L 取得最小值。

另外,假设L*是Q(L) = 0时的最优解:

Q(L) > 0
当且仅当
L < L*

Q(L) = 0
当且仅当
L = L*

Q(L) < 0
当且仅当
L > L*


现在我们可以通过二分法来寻找R值或者通过Dinkelbach算法迭代求解。

不同的情况下,两种算法会发挥不同的效果,视情况而定。


传送门:【POJ】2728 Desert King


题目大意:给你一个无向完全图,每条边i都有两个权值,长度a[ i ],花费b[ i ],需要选出其中的一些边构造一颗生成树,生成树需要满足条件:∑ b [ i ] / ∑ a [ i ]最小。


题目分析:01分数规划——最优比率生成树。经典题!!!

本题二分明显没有迭代的效率高。

二分解法:

求出Q(L) = height[ i ] - R * length[ i ]

Q(L) <= 0 则移动上界,否则移动下界


二分代码:


//1454ms
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REPV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define clear( a , x ) memset ( a , x , sizeof a )const int MAXN = 1005 ;
const double INF = 1e18 ;
const double eps = 1e-5 ;struct Point {double x , y , h ;void input () {scanf ( "%lf%lf%lf" , &x , &y , &h ) ;}
} ;struct MST {Point point[MAXN] ;double G[MAXN][MAXN] ;double length[MAXN][MAXN] ;double height[MAXN][MAXN] ;double d[MAXN] ;bool vis[MAXN] ;int fa[MAXN] ;int n ;double dist ( double x , double y ) {return sqrt ( x * x + y * y ) ;}void input () {REP ( i , n )point[i].input () ;REPF ( i , 0 , n - 1 )REPF ( j , i + 1 , n - 1 ) {length[i][j] = length[j][i] = dist ( point[i].x - point[j].x , point[i].y - point[j].y ) ;height[i][j] = height[j][i] = fabs ( point[i].h - point[j].h ) ;}REP ( i , n )height[i][i] = length[i][i] = G[i][i] = 0 ;}void cal ( double r ) {REPF ( i , 0 , n - 1 )REPF ( j , i + 1 , n - 1 )G[i][j] = G[j][i] = height[i][j] - r * length[i][j] ;}double prim ( double r ) {cal ( r ) ;REP ( i , n )d[i] = INF ;clear ( vis , 0 ) ;d[0] = 0 ;fa[0] = 0 ;double ans = 0 , m ;int x ;REP ( _ , n ) {m = INF ;REP ( i , n )if ( !vis[i] && m > d[i] )m = d[x = i] ;vis[x] = 1 ;ans += m ;REP ( i , n )if ( !vis[i] && d[i] > G[x][i] )d[i] = G[x][i] , fa[i] = x ;}return ans ;}void solve () {input () ;double mid , l = 0 , r = 100 ;while ( fabs ( r - l ) > eps ) {mid = ( l + r ) / 2 ;if ( prim ( mid ) <= eps )r = mid ;elsel = mid ;}printf ( "%.3f\n" , l ) ;}
} ;MST z ;int main () {while ( ~scanf ( "%d" , &z.n ) && z.n )z.solve () ;return 0 ;
}



Dinkelbach算法:

设初值0,第一次带入求出的Q(L)一定大于0,但是得到的L带入第二次得到的一定小于0,然后就不断的迭代直到Q(L) = 0。


迭代代码:


//282ms
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REPV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define clear( a , x ) memset ( a , x , sizeof a )const int MAXN = 1005 ;
const double INF = 1e18 ;
const double eps = 1e-5 ;struct Point {double x , y , h ;void input () {scanf ( "%lf%lf%lf" , &x , &y , &h ) ;}
} ;struct MST {Point point[MAXN] ;double G[MAXN][MAXN] ;double length[MAXN][MAXN] ;double height[MAXN][MAXN] ;double d[MAXN] ;bool vis[MAXN] ;int fa[MAXN] ;int n ;double dist ( double x , double y ) {return sqrt ( x * x + y * y ) ;}void input () {REP ( i , n )point[i].input () ;REPF ( i , 0 , n - 1 )REPF ( j , i + 1 , n - 1 ) {length[i][j] = length[j][i] = dist ( point[i].x - point[j].x , point[i].y - point[j].y ) ;height[i][j] = height[j][i] = fabs ( point[i].h - point[j].h ) ;}REP ( i , n )height[i][i] = length[i][i] = G[i][i] = 0 ;}void cal ( double r ) {REPF ( i , 0 , n - 1 )REPF ( j , i + 1 , n - 1 )G[i][j] = G[j][i] = height[i][j] - r * length[i][j] ;}double prim ( double r ) {cal ( r ) ;REP ( i , n )d[i] = INF ;clear ( vis , 0 ) ;d[0] = 0 ;fa[0] = 0 ;double a = 0 , b = 0 , m ;int x ;REP ( _ , n ) {m = INF ;REP ( i , n )if ( !vis[i] && m > d[i] )m = d[x = i] ;a += length[fa[x]][x] ;b += height[fa[x]][x] ;vis[x] = 1 ;REP ( i , n )if ( !vis[i] && d[i] > G[x][i] )d[i] = G[x][i] , fa[i] = x ;}return b / a ;}void solve () {input () ;double res = 0 , tmp ;while ( 1 ) {tmp = prim ( res ) ;if ( fabs ( tmp - res ) <= eps )break ;res = tmp ;}printf ( "%.3f\n" , res ) ;}
} ;MST z ;int main () {while ( ~scanf ( "%d" , &z.n ) && z.n )z.solve () ;return 0 ;
}


这篇关于【POJ】2728 Desert King 最优比率生成树——01分数规划【经典】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1139371

相关文章

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人,是不是经常需要制作各种PPT来分享我的生活和想法。但是,你们知道,有时候灵感来了,时间却不够用了!😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手!🌟 什么是Kimi? 一款月之暗面科技有限公司开发的AI办公工具,帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师,Kimi都能够为你的办公文

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据,将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D