我决定深入学习回溯的概念，我有以下任务：
给定n个投资者，m个城市，n个投资者偏好的m矩阵p（p[i，j]=1，当i-th投资者希望在j-th城市建立投资池时；p[i，j]=0，那么他是中立的，当p[i，j]=-1时，他是怀疑的）和接受水平l（如果对于给定的地点选择，投资者偏好的总和大于或等于L，我们认为他是确信的）找出可以说服的投资者的最大数量和应该在其中建立资金池的城市。
我试过使用回溯，但我想知道是否有可能优化它更多现在，在每个递归级别上，我都会跟踪有多少人可能被说服。如果这个数字小于或等于我当前的最大值，那么我返回（没有更好的答案）。
最佳答案
我不确定这是否是你要找的，但是只要一个小技巧，你就可以把问题表示成一个整数线性规划（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]表示是否在城市中建立一个投资池。
这个问题的公式是ILPs的标准形式，所以您可以去。
关于algorithm - 投资者和资金池-回溯，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36673444/