配置优化算法

Question

我正在尝试计算出满足一套标准的产品的最便宜配置的最佳方法。

想象一下以下产品：

产品1 - $ 1000个 -

Attribute 1 x 1 
Attribute 2 x 5 

产品2 - $ 75 -

Attribute 2 x 1 

产品3 - $ 3000 -

Attribute 1 x 1 
Attribute 2 x 10 
Attribute 3 x 1 

而且以下荷兰国际集团的要求：

1x Attribute 1 
10x Attribute 2 

显然这里的最佳解决方案是1x Product 1和5x Product 2，但我需要解决这个问题时，我有几十种产品和要求。

对不起，如果我没有解释得很好，我真的很感激任何关于计算这个最好的方法的建议。

感谢，

安东尼

编辑：

我之前发布的看着背包问题，但是与该方法的问题是，我没有上限（容量）并且每个项目属性没有设定值。比如我可能有第四个产品：

产品4 - $ 500 - $

Attribute 2 x 10 

所以现在属性2价值$ 75时，单数或10的倍数拿来当，这么清楚，如果我想10 $ 50属性2我想获得单个产品4而不是产品2的10个，在这个例子中，我可以使用value x quantity来确定属性的权重，但是我不能用这种方法计算一些属性，例如产品1，因为我没有办法确定属性1的值（它只能用于其他属性）。

Answer 1

你在这里修改的是knapsack problem，你有几种不同的力量（在这种情况下是你在开始时的每个属性的数量）。它可以使用动态编程来解决。我建议你阅读有关背包问题的文章，并了解我们如何处理它。由于您没有显示任何尝试解决方案，我故意只给您一个提示。

编辑：实际上你的问题是相当接近于背包问题的一个着名的变化，即change making problem。将产品视为可用的硬币价值，但在选择产品时应将其计算为产品价格的“硬币”数量。