我无法将此问题与某个规范问题进行匹配,我希望有一些指导来构建/使用算法并解决它说明如下:
我们有些人想吃早餐。每人可以点任意数量的咖啡、果汁和吐司。我们为所有小组累积订单。
InitialOrder = { C1, J1, T1 } with C1, J1, T1 being integer non-negative numbers.
每个组件都有一个给定的价格,因此初始订单的总价为
InitialPrice = C1 * Pc + J1 * Pj + T1 * Pt with Pc, Pj, Pt being rational positive numbers
自助餐厅也有“早餐菜单”,包括标准项目的组合
丰盛早餐=咖啡+果汁+吐司
普通早餐=咖啡+吐司
面包早餐=2吐司
选择这些菜单比单独选择每个组件要便宜,所以我们有
pfPn铅<2*Pt
Pf,Pn,Pb为有理正数
人们希望将最初的订单分组到菜单中,以最小化总花费那么
FinalOrder = { C2, J2, T2, F, N, B } with C2, J2, T2, F, N, B integer non-negative numbers
我们会有一个最终价格FinalPrice = C2 * Pc + J2 * Pj + T2 * Pt + F * Pf + N * Pn + B * Pb with Pc, Pj, Pt, Pf, Pn, Pb as rational positive numbers
所有价格(Pc、Pj、Pt、Pf、Pn和Pb)都是事先知道的。
请问,你知道我应该遵循哪种方法来建立一个算法来最小化给定初始订单的最终价格吗请随时询问您需要的更多细节。
提前谢谢你。

最佳答案

这看起来是个Linear Integer Programming问题。
你有六个变量和一个线性方程(最终价格),你需要最小化,给定的线性约束(必须匹配初始顺序)限制条件是变量为非负并取整数值。
例如,在你的例子中,它将是(我认为你的实际问题比你的例子更复杂:-)
减少

C2 * Pc + J2 * Pj + T2 * Pt + F * Pf + N * Pn + B * Pb

(如果需要,将Pc etc与适当的整数相乘,使之成为整数)
受制于
   C2 + F + N = C1
   T2 + F + N + 2B = T1
   J2 + F = J1

在一般情况下,整数规划是NP难的,但是考虑到问题的规模和约束条件,标准的求解技术很可能可以为您快速地解决它。
希望能有所帮助。

10-06 10:42