JavaScript中具有多个约束的优化/背包算法 [英] Optimisation/knapsack algorithm with multiple contraints in JavaScript

问题描述

我正在寻找解决多重约束的背包问题的解决方案.

I'm looking for a solution to the knapsack problem where multiple constraints are in place.

说我们的背包最大重量为30公斤，我们有100个物品，每个物品都有重量，每个物品都有好处.这些对象可能看起来像这样:

Say our knapsack has a maximum weight of 30kg and we have a set of 100 objects, each with a weight and each with a benefit. These objects could look like this:

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

在最大重量范围内找到具有最大益处的对象组合非常简单.这是一个nodeJS插件，展示了如何完成... https://gist.github.com/danwoods/7496329

Finding the combination of objects with the highest benefit within the maximum weight is simple enough. Here is a nodeJS plugin showing how it can be done... https://gist.github.com/danwoods/7496329

当对象具有更多属性而背包有更多限制时，我却在苦苦挣扎.

Where I'm struggling is when the objects have more properties and the knapsack has more limitations.

约束: 最大重量为 30 ， 完全使用 8 个对象， 最多使用 3 个对象类型"， 最多使用 3 个对象颜色"

Constraints: Max weight of 30, Use exactly 8 objects, Use a maximum of 3 of any object 'type', Use a maximum of 3 of any object 'colour'

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

如何使用这些额外的规则找到最佳的对象组合?

How can the optimal combination of objects be found with these extra rules in place?

是否可以修改上面链接的背包解算器，还是需要一种新方法?

Can the knapsack solver linked to above be modified or is a new approach needed?

推荐答案

也许这对您的代码无济于事，但可以帮助您对问题进行建模. 可以说决策变量是x [i] =二进制.

Maybe this won't help your code, but it can help to modeling your problem. lets say decision variable is x[i] = binary.

最大容量:

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

恰好使用8个对象:

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

使用最多3个对象类型:

use max 3 object type:

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

使用最多3种对象颜色:

use max 3 object color:

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

这篇关于JavaScript中具有多个约束的优化/背包算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！