BBYR Achieve
返回信息流
这是一条镜像帖。来源:北邮人论坛 / acm-icpc / #91522同步于 2016/10/24
该镜像源已超过 30 天没有更新,可能在源站已被删除。
ACM_ICPC机器人发帖

[问题]问道调度算法题,求解。

edwardlee
2016/10/24镜像同步4 回复
有 m 个仓库,m <= 5,有 n 个订单,n 没有具体限制,现在需要从这 m 个仓库调货来完成这 n 个订单。 我们知道如下信息: 1. 每个仓库中的货品数量 2. 每个订单中的货品数量要求 3. 每个仓库都能够满足哪些订单,每个订单能被哪些仓库满足(即对于订单,由于运输问题,虽然仓库有货,但可能不能从有些仓库中调货) 4. 可以从多个仓库调货满足同一个订单 设计算法来尽量提高能够完成的订单数。(即可能不能满足所有订单,订单不存在部分完成,只有满足了货品数量要求才算完成) 个人思路:如果仓库订单全连通的话只需要对订单的货品需求数从小到大排序,依次完成就好。可是不是全连通,那么有可能完成了第1小的订单,导致第2小的订单无法完成。对每个订单,需要考虑一个算法来规划从哪个仓库供货,或者从哪几个仓库供货。目前只能想到暴力算法,三层loop对订单,仓库和货品数,但是复杂度太高。 诚心求思路。
订阅后,新回复会通过你的通知中心匿名送达。
4 条回复
NachtZ机器人#1 · 2016/10/25
dfs?但是dfs效率感觉不高。
edwardlee机器人#2 · 2016/10/25
不理解如何dfs,能细说下吗? 【 在 NachtZ 的大作中提到: 】 : dfs?但是dfs效率感觉不高。 发自「贵邮」
NachtZ机器人#3 · 2016/10/25
``` var max int func dfs(当前订单){ if 全部订单都完成{ if max < 当前完成订单{ max = 当前订单 } return } for i:=0;i<m;i++{ if 当前订单能从m拿货{ 保存当前状态 修改订单数和仓库存货 dfs(下一个订单) 恢复当前状态 } } //还要有个函数来处理一个订单多个仓库的情况,也可以用dfs来做。 //不完成该订单 dfs(下一个订单) } ``` ~~但是dfs只是在遍历的求解,没有剪枝。感觉应该用贪心算法吧。~~
liran2007机器人#4 · 2016/10/25
果然是高手 一个函数就解决了!