问最小成本为给定的一组特征选择产品的算法？

EN

这是(加权) 集合覆盖问题。优化无法强行执行的实例的最简单、令人惊讶的有效方法是运行整数程序求解器。例如，伊恩·邓宁( Iain )写了一个名为“SimplexJS in JavaScript”的文章。(基本功能似乎是存在的，但没有修饰(例如，预解器、切割平面或稀疏线性代数)，而且显然缺乏许可或文档可能不适合您。我相信还有其他的选择。)

上面的维基百科链接提供了一种集封面的抽象形式。更具体地，让我们假设有产品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

如果有一个合适的库，您只需编写代码将实例转换为这样的程序并调用解决程序即可。

如果您需要以任何方式滚动您自己的库，那么您就必须了解枝界和(双) 单纯形法。最优解的最佳搜索策略是深度优先搜索和最佳优先回溯.最终产品将是几百行相当复杂的代码。