分数规划题解1
需积分: 0 58 浏览量
2022-08-03
11:19:14
上传
评论
收藏 206KB PDF 举报
http://pan.baidu.com/s/1dDtaYuH 题解代码包下载地址
POJ2976【基础】
题目大意：
给出两个数组 a[i]、b[i]，这两个数组里的数都是整数，一共有 N
（1<=n<=1000）个，要从里面去掉 K（1<=K<N）对数（去掉一对数的意思是同
时去掉 a[i]和 b[i]），使得剩下来的数满足 T=simga(a[i])/sigma(b[i])最
大。
输入：
有若干组测试数据。每一组测试数据的第一行有两个整数 N 和 K，接下来有两
行，分别是 a[i]和 b[i]。N=K=0 时输出结束。
输出：
每一组数据输出一行，包含一个整数，即对 T*100 四舍五入。
题解：
这是一题经典（裸）的 01 分数规划问题。关于分数规划，在胡伯涛的最小割论
文里面有，网上也有一个更浅显一些的讲解在
http://blog.csdn.net/hhaile/article/details/8883652。这一题的代码我用
的是二分法写的。
POJ3757【基础】
题目大意：
一种分布式文件存储系统由一个调度服务器和 N 台（1<=N<=20000）后端服务器
节点组成。现在调度服务器收到一个一个大小为 F MB 的文件请求，而这个文件
在每一台后端服务器上都有完整的存储，需要选择 K 个后端服务器来传送 K 个
分块的文件，并且这 K 个分块的文件大小需要相同。每一个后端服务器有三个
参数 P、B 和 C，表示数据 IO 吞吐速度（MB/s），和调度服务器的传输速度
（MB/s）以及传输每 MB 文件所需要的花费。求如何选择，才能令总的传输花费
最小。假定 F MB 的文件总能被平均分为 K 块。
输入：
第一行有两个整数和一个小数，分别是 N、K 和 F。
普通网友
- 粉丝: 17
- 资源: 314
评论0