建模组合优化？问题
我无法将这个问题与某个规范问题相匹配，我想要一些指南来构建/使用算法并解决它。描述如下：
我们有一些人想要早餐。每人可以点任意数量的咖啡、果汁和吐司。我们累积所有组的订单。
InitialOrder = { C1, J1, T1 } 其中 C1, J1, T1 为非负整数。
每个组件都有一个给定的价格，因此初始订单的总价为
InitialPrice = C1 * Pc + J1 * Pj + T1 * Pt，其中 Pc、Pj、Pt 为有理正数
自助餐厅也有由标准项目组合而成的“早餐菜单”
full breakfast = coffee + juice + toast normal breakfast = coffee + toast bread breakfast = 2 toast
选择这些菜单比单独选择每个组件便宜，因此 人们希望
Pf < Pc + Pj + Pt Pn < Pc + Pt Pb < 2 * Pt with Pf, Pn, Pb being rational positive numbers
将最初的订单分组到菜单中，以尽量减少总花费。然后
FinalOrder = { C2, J2, T2, F, N, B } 与 C2, J2, T2, F, N, B 整数非负数
我们将得到 FinalPrice <=初始价格为
FinalPrice = C2 * Pc + J2 * Pj + T2 * Pt + F * Pf + N * Pn + B * Pb，其中 Pc、Pj、Pt、Pf、Pn、Pb 为有理正数
所有价格（Pc、Pj、Pt、Pf、Pn 和 Pb）均预先已知。
请问，您知道我应该遵循哪种方法来构建一个算法来最小化给定初始订单的最终价格？请随时询问您需要的更多详细信息。
先感谢您。
I've been unable to match this problem into some canonical one, and I would like some guides to build/use an algorithm and solve it. Description is as follows:
We have some people who want breakfast. Each one may order any number of coffee, juice and toast. We accumulate the order for all the group.
InitialOrder = { C1, J1, T1 } with C1, J1, T1 being integer non-negative numbers.
Each component has a given price, so the total price of the initial order is
InitialPrice = C1 * Pc + J1 * Pj + T1 * Pt with Pc, Pj, Pt being rational positive numbers
Cafeteria has also 'breakfast menus' consisting in combinations of standard items
full breakfast = coffee + juice + toast normal breakfast = coffee + toast bread breakfast = 2 toast
Choosing these menus is cheaper than choosing each component separately, so we have
Pf < Pc + Pj + Pt Pn < Pc + Pt Pb < 2 * Pt with Pf, Pn, Pb being rational positive numbers
People want to group the initial order into menus to minimize the total amount spent. Then
FinalOrder = { C2, J2, T2, F, N, B } with C2, J2, T2, F, N, B integer non-negative numbers
and we'll have a FinalPrice <= InitialPrice as
FinalPrice = C2 * Pc + J2 * Pj + T2 * Pt + F * Pf + N * Pn + B * Pb with Pc, Pj, Pt, Pf, Pn, Pb as rational positive numbers
All prices (Pc, Pj, Pt, Pf, Pn and Pb) are known in advance.
Please, do you know Which approach should I follow to build an algorithm to minimize FinalPrice for a given InitialOrder? Feel free to ask any more details you need.
Thank you in advance.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这看起来像是一个线性整数规划问题。
您有六个变量和一个线性方程（最终价格），在给定线性约束（必须与初始顺序匹配）的情况下，您需要将其最小化。限制是变量是非负的并且取整数值。
例如，在您的示例情况下，它将是（我假设您的实际问题比您的示例更复杂:-)）
最小化
（将 Pc 等与合适的整数相乘，如果需要，使它们成为整数）
受到
一般情况下的 约束在这种情况下，整数规划是 NP 困难的，但考虑到问题的规模和限制，标准求解技术可能可以快速为您解决它。
希望有帮助。
This looks like a Linear Integer Programming problem.
You have six variables and a linear equation (for final price) which you need to minimize, given linear constraints (must match initial order). The restriction being that the variables are non-negative and take integer values.
For instance in your example case it will be (I am presuming your actual problem is more complicated than your example :-))
Minimize
(Multiply Pc etc with a suitable integer to make them integers if needed)
Subject to the constraints that
In the general case, Integer Programming is NP-Hard, but given the small size of the problem and the constraints, standard solving techniques can probably quickly solve it for you.
Hope that helps.
如果您不想全力以赴（整数线性规划，这是一个相当复杂的领域），请考虑使用分支定界进行详尽的树搜索。 BnB 本质上是深度优先搜索，当当前分支的成本大于或等于迄今为止找到的最佳解决方案时，您可以回溯。
不过，正如 Moron 所说，对于任何大问题，您都需要 ILP。
If you don't want to go the whole hog (integer linear programming, which is a reasonably complex area), consider an exhaustive tree search using branch-and-bound. BnB is essentially depth-first search where you backtrack at any point where the cost of the current branch is greater than or equal to the best solution you have found so far.
As Moron says, though, for any large problem you're going to need ILP.
由于您的问题与装箱（或至少是它的矢量版本）密切相关，因此一些相关的启发式方法也可能会派上用场。具体来说，一种贪婪的启发式方法，即首先贪婪地打包全套早餐（或 2*普通早餐 + 烤面包，具体取决于相对成本），然后继续这样做，可能就足够了。
Since your problem is closely related to bin packing (or at least the vector version of it), some of the associated heuristics might also come in handy. Specifically, a greedy heuristic where you greedily pack full breakfasts (or 2*normal + toast depending on the relative costs) first, and then continue in this vein, might suffice.