algorithm - 投资者和资金池 - 回溯

Question

我决定深入学习回溯的概念，我有以下任务:

给定N个投资者，M个城市，N×M个投资者偏好矩阵P(P[i,j]=1，当第i个投资者希望在第j个城市建矿池；P[i, j] = 0 那么他是中立的，当 P[i, j] = -1 他是怀疑的)和接受水平 L(如果对于给定的地点选择，投资者偏好的总和大于或等于 L 那么我们认为他是相信的).找到可以说服的最大数量的投资者和应该建立资金池的城市。

我尝试过使用回溯，但我想知道是否有可能对其进行更多优化。现在，在每个递归级别上，我都会跟踪可以说服多少人。如果这个数字小于或等于我当前的最大值，那么我返回(没有更好的答案)。

Answer 1

我不确定这是否是您要查找的内容，但通过一些小技巧，您可以将问题表示为整数线性程序 (ILP)。然后，您可以使用整数线性规划求解器(例如 GLPK)找到最优解。

设s[i] 为0-1 整数变量(i 取值范围为investors)，c[j] 为0-1城市范围内的整数变量，K是一个很大的数字(L + 投资者数量即可)。

然后，你的问题是最小化 sum(s[i]) 这样对于每个 i，sum(P[i, j]*c [j]) + s[i] * K >= L。最优解中sum(s[i])的值为不满意的投资者数量，c[j]表示是否在city中建池j.

这个问题的表述是 ILP 的标准形式，所以你可以开始了。