配置優化算法

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。將產品視爲可用的硬幣價值，但在選擇產品時應將其計算爲產品價格的「硬幣」數量。