返回信息流1.现有一跨国公司，在全球设立了M个仓库，分别向各自所辖地区（两个仓库的辖区有可能有部分重叠）经销商提供商品。每个仓库能容纳的商品数量均为P。
2、每个仓库安排有大车C1辆，小车C2辆。其中一辆大车的容量为P1，一辆小车的容量为P2。即 C1*P1 + C2*P2 = P。
3、现在全球范围内共有N个经销商，一个经销商只能从一个仓库进货。提供每个仓库与经销商的关系（注意有的经销商只有一个可选择的仓库，有的经销商有多个可选择的仓库，但是最终只能选择一个仓库进货）。
4、每辆车的配送方式为：车辆将商品载到某个集散地（某一位置）后，以该地点为中心，某一长度为半径画圆，然后在该圆范围内的经销商自己来领取所需商品。其中，大车的半径为R1，小车的配送半径为R2。
5、现在经销商要向总部提出货单，表示需要进货的商品数量Si(0<i<N), Si的值不会超过小车的容量（即一个经销商最多占用一辆车）。
6、总部收到各经销商的货单之后，通过计算，决定派遣哪些仓库的哪些车辆，每辆车上分.装载多少商品，以及送往的集散地的具体位置。
7、问题来了，如何设计整套算法，可以使得最后所有经销商能获得到的商品数量总和最大。
********************************************************
问题简化成：
a、每个仓库Wi均包含辖区半径R，且均持有大车C1辆，小车C2辆，及其各自的容量P1、P2，配送半径R1、R2（配送半径是以集散地为中心而不是以仓库位置为中心。
b、总部持有所有仓库及经销商的位置信息（经纬度）。结合仓库辖区半径，可以得出每个仓库与经销商之间的配对关系（注意最后一个经销商只能由一个仓库的一辆车提供商品）。
c、总部根据每个经销商提出的货单申请Si，依据条件a和b，决定配送方案。
d、假设最后每个经销商能得到的商品数量为Ti，问如何设计算法，可以使得Ti的和最大。
我觉得好难啊，有没有算法大神带我起飞[ema0][ema0][ema0]？
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #91141同步于 2016/9/20
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
一道超级难的资源分配问题
akhyx
2016/9/20镜像同步2 回复
订阅后，新回复会通过你的通知中心匿名送达。
2 条回复