algorithm - 比抛硬币游戏的蛮力算法更好

Question

我有一个问题，我觉得应该有一个众所周知的算法来解决它，它比蛮力更好，但我想不出一个，所以我在这里问。
问题如下:给定 n包含 m 的排序(从低到高)列表概率，为每个列表选择一个索引，使得所选索引的总和小于 m .然后，对于每个列表，我们抛硬币，其中正面朝上的机会等于该列表所选索引的概率。最大化硬币着陆头至少一次的机会。
有没有比暴力破解更好的算法来解决这个问题？
这个问题似乎与背包问题最相似，只是背包中物品的值(value)不仅仅是背包中物品的总和。 (用 Python 编写，而不是 sum(p for p in chosen_probabilities) 是 1 - math.prod([1 - p for p in chosen_probabilities]) )而且，鉴于背包中已有哪些物品，您可以添加哪些物品。例如，如果 index = 3特定列表的项目已在背包中，然后使用 index = 2 添加项目对于同一个列表是不允许的(因为您只能为每个列表选择一个索引)。因此，根据背包中已有的物品，某些物品可以和不能添加到背包中。
线性优化不起作用，因为列表中的值不会线性增加，最终硬币概率与所选概率不是线性的，我们的约束是索引的总和，而不是列表中的值列出自己。正如大卫所指出的那样，如果您使用二进制变量来挑选索引并使用对数来处理非线性，则线性优化将起作用。
编辑:
我发现解释这个问题背后的动机有助于理解它。想象一下，你有 10 秒的时间来解决一个问题，并且有三种不同的方法来解决它。您有每种方法解决问题的可能性的模型，考虑到您尝试该方法的秒数，但是如果您切换方法，您将失去之前尝试的方法的所有进度。您应该尝试哪些方法以及持续多长时间？

Answer 1

最大化 1 - math.prod([1 - p for p in chosen_probabilities])相当于最小化 math.prod([1 - p for p in chosen_probabilities]) ，这相当于最小化这个目标的对数，它是一个 0-1 指标变量的线性函数，所以你可以用这种方式做一个整数规划公式。
我不能保证这会比蛮力好得多。问题是math.log(1 - p)很好地近似于 -p当p接近于零。我的直觉是，对于非平凡的实例，它在性质上类似于使用整数规划来解决子集和，这不是特别好。
如果您愿意接受双标准近似方案(得到一个答案，使得所选索引的总和小于 m，这至少与总和小于 (1 − ε) m 的最佳答案一样好)那么您可以将概率四舍五入为 ε 的倍数，并使用动态规划来获得一个以 n、m、1/ε 的时间多项式运行的算法。