这个优化算法的正式名称？
Formal name for this optimization algorithm?
我的一个编码项目中存在以下问题，我将在此处简化：
我正在网上订购杂货，想要非常具体数量的非常具体的东西。我想订购以下：
- 8 个苹果
- 1 山药
- 2 汤
- 3 块牛排
- 20 橙汁
有很多商店离我等距，我会从那里送餐。并非所有商店都有我需要的东西。 我想用最少的订单获得我需要的东西。例如，从下面的 #2 商店订购是浪费订单，因为我可以通过订购以更少的订单完成我的商品来自不同的商店。 解决这个问题的优化算法的名称是什么？
商店 #1 供应
- 50 个苹果
商店 #2 供应
1 橙汁
2 块牛排
1汤
商店 #3 供应
25汤
50 橙汁
商店 #4 供应
25块牛排
10 颗山药
在这种情况下，可能的最低订单是 3。 1 号商店的 8 个苹果。 3 号商店的 2 份汤和 20 份橙汁。 4 号店的 1 个山药和 3 个牛排。
对我来说，这很可能听起来像是 Integer Linear programming problem (ILP) 的受限情况，即它的 0 或 1 变体，其中整数变量被限制在集合 {0, 1} 中。这被称为 NP-hard（并且相应的决策问题是 NP-complete）。
问题表述如下（遵循引文中的惯例）：
Given the matrix A, the constraint vector b, and the weight vector c, find the vector x ∈ {0, 1}N such that all the constraints A⋅x ≥ b are satisfied, and the cost c⋅x is minimal.
我翻转了约束不等式，但这相当于改变A和[=的符号42=]b.
不等式表示您对订单的满意度：您至少可以购买所访问商店中每件商品的数量。请注意 b 的长度与 A[ 中的行数相同=57=] 以及 c 和 x[ 中的列数=57=]。点积 c⋅x 自然是一个标量。
由于您要尽量减少行程次数，因此每次行程的费用相同，因此 c =1 ，而c⋅x是总行程数。商店库存矩阵 A 每个项目一行，每个商店一列，b 是您的购物清单。
当然，通过尝试 [=42 的所有可能的 2N 值可以找到确切的最佳解决方案=]x.
由于 NP-hard 问题没有单一的方法，请考虑问题的大小，以及您想要达到的最优值的接近程度。当 "inventories" 很大时，贪婪的方法会很有效（当您下一个要访问的商店的商品总数最多时尚未满足）。如果您事先知道预期的最小行程数，您可以 trim 搜索波束的某个值，超出行程数乘以某个乘数。当您的搜索受到时间限制时，这是最好的方法（我经常进行束搜索，与文章中提到的分支切割方法密切相关，在占用几 GB 内存的图表中略快于 30 毫秒的限制光束宽达 10,000 的探索步骤）。如果搜索环境不太粗糙，模拟退火也有效。
还有search on cs.SE；对于此类问题，它可能是一个更好的地方。
我的一个编码项目中存在以下问题，我将在此处简化：
我正在网上订购杂货，想要非常具体数量的非常具体的东西。我想订购以下：
- 8 个苹果
- 1 山药
- 2 汤
- 3 块牛排
- 20 橙汁
有很多商店离我等距，我会从那里送餐。并非所有商店都有我需要的东西。 我想用最少的订单获得我需要的东西。例如，从下面的 #2 商店订购是浪费订单，因为我可以通过订购以更少的订单完成我的商品来自不同的商店。 解决这个问题的优化算法的名称是什么？
商店 #1 供应
- 50 个苹果
商店 #2 供应
1 橙汁
2 块牛排
1汤
商店 #3 供应
25汤
50 橙汁
商店 #4 供应
25块牛排
10 颗山药
在这种情况下，可能的最低订单是 3。 1 号商店的 8 个苹果。 3 号商店的 2 份汤和 20 份橙汁。 4 号店的 1 个山药和 3 个牛排。
对我来说，这很可能听起来像是 Integer Linear programming problem (ILP) 的受限情况，即它的 0 或 1 变体，其中整数变量被限制在集合 {0, 1} 中。这被称为 NP-hard（并且相应的决策问题是 NP-complete）。
问题表述如下（遵循引文中的惯例）：
Given the matrix A, the constraint vector b, and the weight vector c, find the vector x ∈ {0, 1}N such that all the constraints A⋅x ≥ b are satisfied, and the cost c⋅x is minimal.
我翻转了约束不等式，但这相当于改变A和[=的符号42=]b.
不等式表示您对订单的满意度：您至少可以购买所访问商店中每件商品的数量。请注意 b 的长度与 A[ 中的行数相同=57=] 以及 c 和 x[ 中的列数=57=]。点积 c⋅x 自然是一个标量。
由于您要尽量减少行程次数，因此每次行程的费用相同，因此 c =1 ，而c⋅x是总行程数。商店库存矩阵 A 每个项目一行，每个商店一列，b 是您的购物清单。
当然，通过尝试 [=42 的所有可能的 2N 值可以找到确切的最佳解决方案=]x.
由于 NP-hard 问题没有单一的方法，请考虑问题的大小，以及您想要达到的最优值的接近程度。当 "inventories" 很大时，贪婪的方法会很有效（当您下一个要访问的商店的商品总数最多时尚未满足）。如果您事先知道预期的最小行程数，您可以 trim 搜索波束的某个值，超出行程数乘以某个乘数。当您的搜索受到时间限制时，这是最好的方法（我经常进行束搜索，与文章中提到的分支切割方法密切相关，在占用几 GB 内存的图表中略快于 30 毫秒的限制光束宽达 10,000 的探索步骤）。如果搜索环境不太粗糙，模拟退火也有效。
还有search on cs.SE；对于此类问题，它可能是一个更好的地方。