algorithm - 寻找最便宜子集的有效算法

Question

主题
我们有一个商品目录 [{id, prodno, qty, price}] 和商品 bundle [{id, price, items:[{prodno, qty}]}].
我们必须找到最便宜的子集 - 结果 {price, [[{id, qty}]]}，其中包含指定的项目 - query [{prodno, qty}].
示例:

items = [
  {id:1, prodno:'A', qty:1, price:1},
  {id:2, prodno:'A', qty:5, price:3},
  {id:3, prodno:'B', qty:10, price:1}
]  
bundles = [
  {id:4, price:3, items:[
    {prodno:'A', qty:2},
    {prodno:'B', qty:5}
  ]}
]  
query = [
  {prodno:'A', qty:5},
  {prodno:'B', qty:4}
]  
result = {price:4, [
  [{id:2, qty:1},{id:3, qty:1}]
]}

我们已请求 5xA 和 4xB 并检索到 1 个最便宜的子集(给出 5xA 和 10xB)。

Answer 1

这本质上是集合 covering problem 的变体.
如果我没记错的话，贪心算法对这类问题效果很好，但可能还有更复杂的算法可以做得更好。