配置优化算法

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美元时值为50美元，如果我想要属性2的10倍值时值为50美元，那么很明显，如果我想要属性2的10，那么我想要得到一个产品4而不是产品2的10，在这个例子中，我可以使用value x quantity来确定属性的权重，但是有些属性我无法用这个方法来计算，比如Product1，因为我无法确定属性1的值(它只能与其他属性一起使用)。

Answer 1

这里所做的是对一个背包问题的修改，其中您有几个不同的擦拭(在本例中，每个属性的数目在开始时)。它可以用动态规划来求解。我建议你阅读这篇关于背包问题的文章，并了解我们如何处理它。我只是故意给你一个提示，因为你没有给出任何尝试的解决方案。

编辑:实际上，您的问题非常接近背包问题的一个著名变体，即变更问题。将产品视为可用的硬币价值，但在选择产品时，将其计算为与产品价格相同的“硬币”。