如何从购物清单的多个捆绑包中找到最便宜的产品组合

Question

假设我有不同的产品组合，每个产品组合都有一个价格。

Name               Price      Products
Fruit Overdose     5$         2 Apples, 1 Orange, 1 Banana
Doctors Darling    1$         1 Apple
The Exotic         3.50$      2 Oranges, 1 Banana
Vitamin C          1.5$       1 Orange

我有一个购物清单，例如我要购买：

4 Apples, 1 Orange, 2 Bananas.

问题

我如何找到最便宜的捆绑包组合来购买给定的购物清单？ 根据购物清单 购买超过要求 是有效的。

我只需要一个与语言无关的提示，告诉我如何最有效地解决这个问题。我的现实世界问题有点复杂，还包括我已经拥有的产品列表；但这应该不是很重要。

Answer 1

这是一个 dual linear programming 问题：

你要最小化的objective就是总价，是一个线性函数
约束可以表示为矩阵方程，其中每一行对应一个捆绑包，每一列对应一种产品。

你可以通过constructing the dual which will be a standard linear programming problem, applying a standard algorithm such as the simplex algorithm来解决它，然后将解决方案转换回原始对偶问题的解决方案。

Answer 2

这种问题用SAT/SMT solver. Z3 is an open source solver with bindings for many languages, including a nicely integrated binding with Python就可以轻松解决了。

在求解器中，您只需声明几个变量（4 个用于每个捆绑包的重量，1 个用于总价）。然后你写下不同的约束。在这种情况下，约束是：

权重应该是正数。
总价的计算方法是将价格乘以每捆重量。
对于每种水果，应购买所需的最少数量。

请注意，我以美分计算价格，以便能够使用整数，尽管这对于 Z3 来说并不是绝对必要的。

Python 代码如下所示：

from z3 import *

bundles = [["Fruit Overdose", 5, {'apple': 2, 'orange': 1, 'banana': 1}],
           ["Doctors Darling", 1, {'apple': 1}],
           ["The Exotic", 3.50, {'orange': 2, 'banana': 1}],
           ["Vitamin C", 1.5, {'orange': 1}]]
desired = {'apple': 4, 'orange': 1, 'banana': 2}
num_bundles = len(bundles)

W = [Int(f'W_{i}') for i in range(len(bundles))]  # weight of each bundle: how many to buy of each bundle
TotalPrice = Int('Total')

s = Optimize()
s.add(TotalPrice == Sum([W[i] * int(b[1] * 100) for i, b in enumerate(bundles)]))
s.add([W[i] >= 0 for i in range(len(W))])  # weights can not be negative
for f in desired:
    s.add(Sum([W[i] * b[2][f]  for i, b in enumerate(bundles) if f in b[2]]) >= desired[f])

h1 = s.minimize(TotalPrice)
result = s.check()
print("optimizer result:", result)
if result == sat:
    s.lower(h1)
    m = s.model()
    print(f"The lowest price is: {m[TotalPrice].as_long()/100:.2f}")
    for i,b in enumerate(bundles):
        print(f"  Buying {m[W[i]].as_long()} of {b[0]}")

输出：

The lowest price is: 10.00
  Buying 2 of Fruit Overdose
  Buying 0 of Doctors Darling
  Buying 0 of The Exotic
  Buying 0 of Vitamin C

如果您只是将 Fruit Overdose 的价格更改为 6，结果将是：

  Buying 0 of Fruit Overdose
  Buying 4 of Doctors Darling
  Buying 2 of The Exotic
  Buying 0 of Vitamin C

算法保证找到最佳解决方案。如果有多个同样好的解决方案，则只返回其中一个。

如何从购物清单的多个捆绑包中找到最便宜的产品组合

How to find the cheapeast combination of products to buy from multiple bundles for a shopping list

language-agnostic

algorithm

math

问题