Алгоритм оптимизации/рюкзака с несколькими ограничениями в JavaScript

Question

Я ищу решение проблемы с рюкзаком, где есть несколько ограничений.

Скажите, что наш рюкзак имеет максимальный вес 30 кг, и у нас есть набор из 100 предметов, каждый с весом и каждый с преимуществом. Эти объекты могут выглядеть так:

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

Поиск комбинации объектов с наибольшим преимуществом в пределах максимального веса достаточно прост. Вот плагин nodeJS, показывающий, как это можно сделать ... https://gist.github.com/danwoods/7496329

Где я боюсь, когда объекты имеют больше свойств, а рюкзак имеет больше ограничений.

Ограничения: Максимальный вес , Используйте точно объектов, Используйте максимум любого 'типа' объект, Используйте максимум любого объекта «цвет '

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

Как можно найти оптимальное сочетание объектов с этими дополнительными правилами?

Может ли модифицированный рюкзак, связанный с ним, модифицироваться или нужен новый подход?

Answer 1

Возможно, это не поможет вашему коду, но это может помочь в моделировании вашей проблемы. позволяет утверждать, что переменная решения 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;