我有一个产品列表和一个功能列表。每个产品都有自己的成本并提供自己的功能子集。
我想要一个算法，这样我可以告诉它我需要哪些功能，它会告诉我需要购买的产品集，以便以最低的总组合成本获得所有这些功能。
有没有人有这样做的秘诀？我想在 JavaScript 中使用它。
问问题
224 次
1 回答
4
这是（加权）集覆盖问题。优化不能被暴力破解的实例的最简单、令人惊讶的有效方法是运行整数程序求解器。例如，Iain Dunning 用 JavaScript 编写了一个名为SimplexJS的程序。（基本功能似乎在那里，但没有多余的装饰（例如，预求解器、切割平面或稀疏线性代数），并且明显缺乏许可证或文档可能不符合您的喜好。我确信那里是替代品。）
上面的 Wikipedia 链接提供了集合封面的抽象表述。更具体地说，假设有产品 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 .
我们为每个产品制作二进制变量 xA、xB、xC、xD。如果我们购买 A，变量 xA 为 1，否则为 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
给定一个合适的库，您只需编写代码将实例翻译成这样的程序并调用求解器。
如果您出于某种原因需要推出自己的库，您将不得不学习分支定界和（双重）单纯形法。求解最优的最佳搜索策略是深度优先搜索和最佳优先回溯。最终产品将是几百行相当复杂的代码。
于 2014-01-22T22:01:04.690 回答