投资者和池-回溯

Question

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

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

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

Answer 1

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

假设s[i]是0-1个整数变量(投资者范围内的i)，c[j]是城市范围内的0-1个整数变量，K是一个大数字(L + the number of investors就可以)。

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

这个问题的公式是ILPs的标准形式，所以您可以开始了。