首页 > 其他分享 >01分数规划入门

01分数规划入门

时间：2022-08-19 17:59:14浏览次数：99  
标签：分数 ch const 入门 int mid read 01 include

01分数规划入门

 

01分数规划，简单的来说，就是有一些二元组（si，pi），从中选取一些二元组，使得∑si / ∑pi最大（最小）。

这种题一类通用的解法就是，我们假设x = ∑si / ∑pi的最大（小）值，那么就有x * ∑pi = ∑si ,即∑si  - x * ∑pi= 0。也就是说，当某一个值x满足上述式子的时候，它就是要求的值。我们可以想到枚举……不过再想想，这个可以二分答案。

所以我们直接二分答案，当上述式子>0,说明答案小了，<0则说明答案大了，这样计算即可。

这是一种解决问题的方法，具体应该怎么做我们要看题来分析。

01分数规划有这样几种基本的题型（当然还有很多别的）

1.01分数规划

2.最优比率生成树

3.最优比率生成环

（当然还有什么最优比率最小割等等……不在juruo当前研究范围之内）

1.01分数规划。

基础题：poj2976

这个就是一开始说的这么一码事……选取n-k（原题是不选k）个物品使得比率最大。

我们考虑对上面的式子进行转化，之后我们只要给每个物品重新赋值为a - x*b，排序之后直接取前n-k大,判断这个值的正负性，然后按上面情况二分即可。

如果不大明白为什么是这么取得的，可以看这里（个人觉得很详细）

附上代码。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('\n')

using namespace std;
typedef long long ll;
const int M = 10005;
const int INF = 1000000009;
const double eps = 1e-6;

int read()
{
    int ans = 0,op = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
    if(ch == '-') op = -1;
    ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
    ans *= 10;
    ans += ch - '0';
    ch = getchar();
    }
    return ans * op;
}

struct test
{
   double a,b,d;
   bool operator < (const test &g) const
   {
      return d > g.d;
   }
}t[1005];

int n,k;
double L,R,ans,mid;

bool pd(double x)
{
   double cur = 0;
   rep(i,1,n) t[i].d = t[i].a - x * t[i].b;
   sort(t+1,t+1+n);
   rep(i,1,n-k) cur += t[i].d;
   return cur >= 0;
}

int main()
{
   while(1)
   {
      n = read(),k = read();
      if(!n && !k) break;
      rep(i,1,n) t[i].a = read();
      rep(i,1,n) t[i].b = read();
      L = 0,R = 1e10;
      while(fabs(R - L) > eps)
      {
     mid = (L + R) / 2.0;
     if(pd(mid)) L = mid;
     else R = mid;
      }
      printf("%.0lf\n",(mid * 100.0));
   }
   return 0;
}

 

2.最优比率生成树。

基础题：poj2728

简单描述就是，每一条路有一个花费p和一个权值s，要在图上选取一些边构成一棵生成树，求生成树的∑pi / ∑si最小值。

我们还是考虑套用上面的模板，其实这个和01分数规划很像的。只要对每条边重新赋一个值，因为这次我们要求的是花费比上权值，所以和上一道题反了过来，赋值是p-x * s。之后因为要求最小，直接求最小生成树即可。判断一下最小生成树的权值和，如果小于0说明答案设大了，否则说明答案设小了。

这道题是完全图，所以我们需要用prim求最小生成树。（突然发现我从来都是用kruskal都没用过prim），但是它的想法其实很简单，我们从任意一个点开始，之后选取一个最近的点，并且用这个点更新其他点的距离，之后再寻找一个更近的点，再去更新距离。它的复杂度是O（n2）的。

看一下代码。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('\n')

using namespace std;
typedef long long ll;
const int M = 1000005;
const int N = 1005;
const int INF = 1000000009;
const double eps = 1e-6;

int read()
{
    int ans = 0,op = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
    if(ch == '-') op = -1;
    ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
    ans *= 10;
    ans += ch - '0';
    ch = getchar();
    }
    return ans * op;
}

struct node
{
   double x,y,z;
}a[N];

int n;
double L,R,mid,dis[1005][1005],hb[1005][1005],map[1005][1005],cur[1005];
bool vis[1005];

double calc(int p,int q)
{
   return sqrt((a[p].x - a[q].x) * (a[p].x - a[q].x) + (a[p].y - a[q].y) * (a[p].y - a[q].y));
}

void init()
{
   rep(i,1,n) scanf("%lf %lf %lf",&a[i].x,&a[i].y,&a[i].z);
   rep(i,1,n)
   rep(j,i+1,n) dis[i][j] = dis[j][i] = calc(i,j),hb[i][j] = hb[j][i] = fabs(a[i].z - a[j].z);
}

double prim()
{
   double ans = 0;
   rep(i,1,n) vis[i] = 0,cur[i] = map[1][i];
   vis[1] = 1;
   rep(i,1,n-1)
   {
      double minn = INF;
      int pos = 0;
      rep(j,1,n) if(!vis[j] && minn > cur[j]) pos = j,minn = cur[j];
      if(minn == INF) break;
      vis[pos] = 1;
      ans += minn;
      rep(j,1,n) if(!vis[j]) cur[j] = min(cur[j],map[pos][j]);
   }
   return ans;
}

bool pd(double x)
{
   rep(i,1,n)
   rep(j,i+1,n) map[i][j] = map[j][i] = hb[i][j] - x * dis[i][j];
   return prim() < 0;
}

int main()
{
   while(1)
   {
      n = read();
      if(!n) break;
      init();
      L = 0,R = 1e7;
      while(fabs(R-L) > eps)
      {
     mid = (L+R) / 2.0;
     if(pd(mid)) R = mid;
     else L = mid;
      }
      printf("%.3lf\n",L);
   }
   return 0;
}
/*
4
0 0 0
0 1 1
1 1 2
1 0 3
4
0 0 0
0 1 1
1 1 2
1 0 3
0

 */

 

3.最优比率生成环。

基本的思想还是一样的，就是对式子进行一下变形。不过这里稍微有一些不同。

最大化的时候，假设最大值为r*，那么就有∑pi / ∑si <= r*，变形之后就有∑si * r* - ∑pi >= 0.

最小化的时候，假设最小值为r*，那么就有∑pi / ∑si >= r*，变形之后就有∑pi - ∑si * r* >= 0.

这个地方很容易给人搞懵……因为其实我们很容易在求值的时候只使用一种变形式子的方法，然后改变二分的方向，不过这样的话计算的结果会出错。

因为这里要判断的不大一样，如果求最大值的时候设小了，那么就会在原图中出现负环。我们把每条边按上述方法重新赋值，之后我们使用基于dfs的spfa去判负环，之后改变二分的值即可。

如果求最小值，也按上述方法赋值，重新计算即可。

例题：天路 观光奶牛

这两道题都是要求最大比率的环，直接按照上述方法求就可以了。

看一下代码。（观光奶牛）

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('\n')

using namespace std;
typedef long long ll;
const int M = 10005;
const int N = 7005;
const int INF = 1000000009;
const double eps = 1e-6;

int read()
{
    int ans = 0,op = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
    if(ch == '-') op = -1;
    ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
    ans *= 10;
    ans += ch - '0';
    ch = getchar();
    }
    return ans * op;
}

struct edge
{
   int to,next;
   double v,t;
}e[M];

int l,p,x,y,ecnt,head[N];
double f[N],z,L,R,mid,dis[N];
bool vis[N];

void add(int x,int y,double z,double a)
{
   e[++ecnt].to = y;
   e[ecnt].v = a;
   e[ecnt].t = z;
   e[ecnt].next = head[x];
   head[x] = ecnt;
}

bool pd(double x,int pos)
{
   vis[pos] = 1;
   for(int i = head[pos];i;i = e[i].next)
   {
      if(dis[e[i].to] > dis[pos] + e[i].t * x - e[i].v)
      {
     if(vis[e[i].to]) return 1;
     dis[e[i].to] = dis[pos] + e[i].t * x - e[i].v;
     if(pd(x,e[i].to)) return 1;
      }
   }
   vis[pos] = 0;
   return 0;
}

int main()
{
   l = read(),p = read();
   rep(i,1,l) scanf("%lf",&f[i]);
   rep(i,1,p) x = read(),y = read(),scanf("%lf",&z),add(x,y,z,f[y]);
   rep(i,1,l) add(0,i,0,0);
   L = 0,R = 1e7;
   while(fabs(R-L) > eps)
   {
      mid = (L+R) / 2.0;
      memset(dis,0x3f,sizeof(dis)),memset(vis,0,sizeof(vis)),dis[0] = 0;
      if(pd(mid,0)) L = mid;
      else R = mid;
   }
   printf("%.2lf\n",L);
   return 0;
}

 

之后还有一道题，01分数规划+树形背包！

传送门

其实这个题好像说难也不难，因为很好想到怎么做，就是01分数规划的常用套路+树形背包。

我们对于每个人重新进行赋值（其实好像大部分的题都可以用分子-分母*进行赋值……）之后直接跑树形背包，求一下跑出来的最大值，然后改变二分的大小。

这题严重卡常，首先你肯定要用dfs序的树背包，不过其实还是卡不过去，即使把二分上界改为4都不行……精度如果低的话还会wa掉，最后只好开了O2.

我们看一下代码。

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('\n')

using namespace std;
typedef long long ll;
const int M = 1000005;
const int N = 3005;
const int INF = 1000000009;
const double eps = 1e-6;

int read()
{
    int ans = 0,op = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
    if(ch == '-') op = -1;
    ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
    ans *= 10;
    ans += ch - '0';
    ch = getchar();
    }
    return ans * op;
}

struct edge
{
   int next,to;
}e[N<<1];

int k,n,head[N],ecnt,dfn[N],pos[N],idx,size[N],x;
double dp[N][N],s[N],p[N],L,R,mid,val[N];
bool vis[N][N];

void add(int x,int y)
{
   e[++ecnt].to = y;
   e[ecnt].next = head[x];
   head[x] = ecnt;
}

void dfs(int x)
{
   dfn[x] = ++idx,pos[idx] = x,size[x] = 1;
   for(int i = head[x];i;i = e[i].next)
   {
      dfs(e[i].to);
      size[x] += size[e[i].to];
   }
}

double DP()
{
   double maxn = -INF;
   memset(dp,-0x3f,sizeof(dp));
   vis[1][0] = 1,dp[1][0] = 0;
   rep(i,1,idx)
   {
      rep(j,0,min(i,k))
      {
     if(!vis[i][j]) continue;
     dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j] + val[pos[i]]);
     dp[i+size[pos[i]]][j] = max(dp[i][j],dp[i+size[pos[i]]][j]);
     vis[i+1][j+1] = vis[i+size[pos[i]]][j] = 1;
      }
   }
   rep(i,1,idx+1) maxn = max(maxn,dp[i][k+1]);
   return maxn;
}

bool pd(double x)
{
   memset(vis,0,sizeof(vis));
   rep(i,1,idx) val[i] = p[i] - x * s[i];
   return DP() > -eps;
}

int main()
{
   k = read(),n = read();
   rep(i,1,n) scanf("%lf %lf",&s[i],&p[i]),x = read(),add(x,i);
   dfs(0);
   L = 0,R = 1e6;
   while(fabs(R-L) > eps)
   {
      mid = (L+R) / 2.0;
      if(pd(mid)) L = mid;
      else R = mid;
   }
   printf("%.3lf\n",L);
   return 0;
}
 

标签：分数,ch,const,入门,int,mid,read,01,include
From： https://www.cnblogs.com/caterpillor/p/16602849.html

相关文章

  • Python小游戏——外星人入侵（保姆级教程）第一章 01 02
    系列文章目录第一章：武装飞船01：创建Pygame窗口以及响应用户输入02：创建设置类Setting()一、前期准备1.语言版本Python3.9.02.编译器Pycharm20223.下载Pygame点击下......
  • Tableau Desktop 2019 for Mac(数据可视化分析)中文版
    TableauDesktop2019forMac是一款方便实用，功能强大的数据可视化分析软件。Tableau利用技术优势，能够将数据图片转化为数据库查询，利用视觉观察图案的天赋能力，识别趋势，在......
  • GBJ1010-ASEMI整流桥GBJ1010
    编辑：llGBJ1010-ASEMI整流桥GBJ1010型号：GBJ1010品牌：ASEMI封装：GBJ-4特性：整流扁桥正向电流：10A反向耐压：1000V恢复时间：ns引脚数量：4芯片个数：4芯片尺寸：102MIL浪涌电流......
  • RabbitMQ 入门系列：1、MQ的应用场景的选择与Rabbit安装
    1、MQ的应用场景的选择：可以参考网上的对比图： 遥想当年，MQ都是MSMQ（微软）的，现在，都不在参考图上了。对MQ的使用，根据应用场景，选择适合的MQ即可，本系列仅介绍RabbitMQ。2、......
  • 【题解】[FARIO2013]Torusia
    通信题，小A和小B迷失在\(4096\times4096\)的方阵中。方阵是循环的，比如\((0,4095)\)的右边是\((0,0)\)，上面是\((4095,4095)\)。两人都不知道自己的绝对位置。每......
  • SpringSecurity 新版2.7以上 快速入门
    SpringSecurity快速入门1、导入依赖<dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-security</artifactId></de......
  • Oracle 解决【ORA-01704:字符串文字太长】
    错误提示：oracle在toad中执行一段sql语句时，出现错误‘ORA-01704：字符串文字太长’。如下图：原因：一般为包含有对CLOB字段的数据操作。如果CLOB字段的内容非常大的时候，会导致S......
  • VS2013+WDK7600 XP环境配置
    前言：环境搭建/编写/调试参考文章：https://www.cnblogs.com/iBinary/p/8290595.html驱动环境搭建WDK7600环境变量配置配置相关WDK7600的目录打开VS2013，新建空项目文件......
  • Jmeter(四十九) - 从入门到精通高级篇 - jmeter使用监视器结果监控tomcat性能（详解教程
    ------------------------------------------------------------------- 转载自：北京-宏哥https://www.cnblogs.com/du-hong/p/13667219.html -------------------------......
  • Docker快速入门--刘清政
    转载：https://www.cnblogs.com/liuqingzheng/p/16315254.html1Docker简介1.1什么是虚拟化​在计算机中，虚拟化（英语：Virtualization）是一种资源管理技术，是将计算机的各......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99