在JavaScript中有多個約束的優化/揹包算法

我正在尋找一個解決方案，其中存在多個約束的揹包問題。在JavaScript中有多個約束的優化/揹包算法

說我們的揹包最大重量爲30公斤，我們有一套100件物品，每件都有一個重量，每個都有一個好處。這些對象可能如下所示：

{ name: 'water bottle', weight: 2, benefit: 5 }, 
{ name: 'potatoes', weight: 10, benefit: 6 }

在最大重量範圍內找到具有最高優勢的對象組合很簡單。這裏是一個nodeJS插件，展示如何完成它... https://gist.github.com/danwoods/7496329

我在掙扎的地方是當對象有更多的屬性，揹包有更多的限制。

限制條件：最大重量的，使用完全相同8個目的，最多使用的任何對象 '類型' 的，最多使用的任何對象的「色'

{ name: 'water bottle', weight: 2, benefit: 5, type: 'drink', colour: 'clear' }, 
{ name: 'potatoes', weight: 10, benefit: 6, type: 'food', colour: 'beige' }

如何通過這些額外的規則找到最佳的物體組合？

可以修改上面鏈接的揹包解算器還是需要一個新的方法？

來源

2017-01-29 tmw

這是一個有趣的問題，但它太寬泛了：我猜你的意思是寫一個有效的算法呢？ - 我的意思是，你可以蠻力這取決於你的搜索空間有多大，多少時間你有空。 – errantlinguist

@errantlinguist是的，我希望在問題中鏈接到的揹包解決方案的變體，其中創建了一個矩陣。這是一個有效的算法，但我一直在努力添加約束。 – tmw

以下是指向GLPK混合整數規劃求解器的JavaScript版本的鏈接：http：//hgourvest.github.io/glpk.js/。這將允許您使用LP（或MIP）來解決您的問題。 –

也許這不會幫助你的代碼，但它可以幫助建模你的問題。可以說決策變量是x [i] =二元。

最大容量：

sum{i in Object} weight[i]*x[i] <=capacity;

使用正好8對象：

sum{i in Object} x[i] = 8;

使用最多3對象類型：

sum{i in object} type[i]*x[i] <=3;

使用最多3對象顏色：

sum{i in Object} color[i]*x[i] <=3;

來源

2017-01-31 15:36:24

在JavaScript中有多個約束的優化/揹包算法

回答

相關問題