我在美国有 10 个仓库。他们每个人可能有也可能没有产品 A、B、C、D、E 库存。有人从我的网站订购了全部五件商品。
我想尽量减少发送的货件数量。如何确定哪些物品要从哪些仓库发货？
例如，某人订购了 A、B、C、D 和 E。
- 我在纽约有 A 和 B（但没有其他）。
- 我有A、B、C
（但没有其他人）在波士顿。
- 我有 D 和 E（但没有其他）
芝加哥。
我正在尝试开发一种算法，该算法将创建从波士顿发货的三件商品和从芝加哥发货的两件商品。
我不想要 2 件来自纽约的物品、1 件来自波士顿的物品和 2 件来自芝加哥的物品。
所有项目都位于一个中央数据库中。
你的问题正是经典的设置覆盖优化问题 http://en.wikipedia.org/wiki/Set_cover_problem，这是 NP 困难的； “宇宙”是用户想要的物品集合，候选集合是仓库。
提出的算法通过@user384706 https://stackoverflow.com/a/11976750/344821 and @Kickaha https://stackoverflow.com/a/11977012/344821 is the 贪心算法 http://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm那里讨论过，这是一个不错的近似值。
如果您想找到实际的最佳解决方案，最好的选择是使用整数线性规划公式 http://en.wikipedia.org/wiki/Set_cover_problem#Integer_linear_program_formulation并插入一些 ILP 求解器。
您说您不关心距离，但如果您这样做，则设置覆盖问题也会影响每个仓库的成本（c(s)在维基页面上）这将代表较远的仓库不太适合挑选。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
