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