Алгоритм выбора продуктов для заданного набора функций при минимальных затратах?

Question

У меня есть список продуктов и список функций. Каждый продукт имеет свои собственные затраты и предоставляет свой собственный набор функций.

Мне нужен алгоритм, который я расскажу ему, какие из функций я требую, и он скажет мне набор продуктов, которые мне нужно купить, чтобы получить все эти функции при самой низкой общей суммарной стоимости.

Есть ли у кого-нибудь рецепт для чего-то подобного? Я хотел бы иметь его в JavaScript.

Answer 1

Это (взвешенный) set cover problem. Самый простой, удивительно эффективный способ оптимизации экземпляров, которые не могут быть грубыми, - запустить целочисленный программный решатель. Например, Iain Dunning написал в JavaScript JavaScript под названием SimplexJS. (Базовая функциональность, похоже, существует, но нет излишеств (например, пресолвера, плоскостей резания или разреженной линейной алгебры), и очевидная нехватка лицензии или документации может быть не по вашему вкусу. Я уверен, что там являются альтернативами.)

В приведенной выше ссылке в Википедии представлена ​​абстрактная формулировка набора обложки. Более конкретно, давайте предположим, что есть продукты A, B, C, D, где соответствующие наборы функций и цены

A: {1, 2, 3}, 9.99 
B: {2, 4}, 7.99 
C: {3, 4}, 6.99 
D: {4, 5}, 8.99 . 

Мы делаем бинарные переменные хА, XB, Xc, XD, один для каждого продукта. Переменная xA равна 1, если мы купим A и 0, если мы этого не сделаем. Наша цель -

minimize 9.99 xA + 7.99 xB + 6.99 xC + 8.99 xD . 

Для каждой функции у нас есть ограничение, требующее от нас приобрести продукт с этой функцией.

1: xA >= 1 
2: xA + xB >= 1 
3: xA + xC >= 1 
4: xB + xC + xD >= 1 
5: xD >= 1 

Учитывая подходящую библиотеку, вы просто должны написать код, чтобы перевести экземпляр в программу, как это и назвать решатель.

Если вам нужна рулонная библиотека по любой причине, вам нужно будет узнать о branch and bound и (двойном) simplex method. Лучшей стратегией поиска для решения оптимальности является поиск по глубине с наилучшим возвратом назад. Конечный продукт будет состоять из нескольких сотен строк довольно сложного кода.