我有一个问题，我觉得应该有一个众所周知的算法来解决这个问题，它不仅比蛮力强，而且我想不到，所以我在这里问。
问题如下：给定n包含m概率的排序列表（从低到高），请为每个列表选择一个索引，以使所选索引的总和小于m。然后，对于每个列表，我们掷一个硬币，其中硬币落下的机会等于该列表在选定索引处的概率。最大化硬币投掷头的机会至少一次。
有没有比蛮力更好的算法来解决这个问题？
这个问题似乎与背包问题最相似，不同之处在于背包中物品的价值不仅仅是背包中物品的总和。（用Python编写，而不是Python编写sum(p for p in chosen_probabilities)的。1 - math.prod([1 - p for p in chosen_probabilities])）而且，鉴于背包中已经有哪些物品，可以添加哪些物品也有限制。例如，如果index = 3背包中已经有特定列表的项目，index = 2则不允许在同一列表中添加带有该项目的项目（因为您只能为每个列表选择一个索引）。因此，根据背包中已有的物品，某些物品可以或不能添加到背包中。
线性优化将不起作用，因为列表中的值不是线性增加的，最终硬币概率相对于所选概率而言不是线性的，并且我们的约束条件是指数的总和，而不是指标中的值列出自己。 正如David所指出的，如果您使用二进制变量来选择索引并使用对数来处理非线性，则线性优化将起作用。
编辑：
我发现，解释此问题背后的动机可能有助于理解它。想象一下，您有10秒的时间来解决问题，并且有三种不同的解决方法。给定您尝试该方法多少秒钟的时间，您就拥有一种模型来确定每种方法解决该问题的可能性的模型，但是如果切换方法，您将失去之前尝试的方法的所有进度。您应该尝试哪种方法，并持续多长时间？
编辑：正如大卫指出，线性优化将起作用
最大化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)可以很好地近似。我的直觉是，对于非平凡的实例，它在质量上类似于使用整数编程来求解子集总和，但效果并不理想。-pp
如果您愿意采用双标准近似方案（得到一个答案，使得所选索引的总和小于m，则至少与最佳答案的总和小于（1-ε）m一样好）那么您可以将概率四舍五入为ε的倍数，然后使用动态编程来获得一种以n，m，1 /ε的时间多项式运行的算法。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句