给定一组约束条件的指派问题

Question

假设我有一组元组，其中第一个索引代表一个集合，第二个索引是该集合中该特定项的值。我想选择元组的组合，以便在给定约束的情况下最大化第二个索引的总和：

集合数必须小于给定的随机数

元组数必须等于给定的随机数

有人把这个问题描述成一个经典的优化问题吗？第二，关于如何继续这方面的工作，有什么建议吗

蛮力： 创建所有组合并消除那些不满足约束的组合。。。然后选择最大和。这对于较小的列表是可行的，但是我的列表往往非常大，如此之大以至于仅仅创建与itertools的组合就可以最大限度地利用cpu

到目前为止，我在python中尝试的是：

def _testing(self, ranks, nroftuples, maxnrofsets):
        tuplelist = [(rank.identifier, rank.factor, ctr) for ctr, rank in enumerate(ranks)]
        import itertools
        allcombinations = list(itertools.combinations(tuplelist, nroftuples))
        filtered = [x for x in allcombinations if len(set([onetuple[0] for onetuple in x])) <= maxnrofsets]
        maxtuple = filtered[0]
        maxsum = sum([onetuple[1] for onetuple in maxtuple])
        for onetuple in filtered:
            if sum([insidetuple[1] for insidetuple in onetuple]) > maxsum:
                maxtuple = onetuple
                maxsum = sum([insidetuple[1] for insidetuple in onetuple])
        return maxtuple

Answer 1

这些约束使得这有点不标准，但在某种程度上，这肯定接近于一些经典的优化问题，如：

• 箱式包装
• 背包

让我们稍微更改一下“set”语言，因为这会与我们试图构建的set混淆。。。所以你有项目，每个项目都有一个值和一个类

您希望从最多M个不同的类中选择确切的N个项目，以便使总价值最大化

让我看看。有一个简单的例子，按值计算，前N个项最多属于M个不同的类。在这种情况下，只要选择这些项目，你就完成了

只有当你必须选择“正确”的类时，它才会变得棘手。比如，如果最高值的项目在一个类中，否则只有低值的项目，对吗

我觉得一般的情况可能是NP难的，这意味着一个精确的算法将是昂贵的，就像你的暴力案例一样。但我们可以尝试启发式：

• 有一种明显的贪婪方法：开始加载价值最高的项目。然后，只要你仍然低于等级限制，继续添加下一个价值最高的项目。继续学习，直到你达到课程限制。现在，从您选择的类中价值最高的项中填充其余项
• 在另一种贪婪的方法中，您只需计算每个类提供的总价值，然后从该排名中获取顶级类，然后从中选择您的项目
• 您应该能够将整个过程表示为一个线性整数程序：

对于每个项目，如果不选择项目，则得到一个二进制变量，该变量为0，如果选择，则为1。让我们把这些变量称为x[i]。让我们为每个类添加一个变量，称之为c[k]

现在我们有了一个目标函数sum(x[i] * value[i])，我们想要最大化它。我们有很多限制：

• sum(x[i]) == N即，精确选择N项
• sum(c[k)] <= M即最多选择M类
• 现在我们需要一点数学来确保c[k]是“活动的”，如果我们有来自该类的项，则为0，否则为：

因此，对于每个类，获取属于该类项的变量x_k[i]。然后添加一组约束：c[k] >= x_k[i]，这意味着一旦从类k中选择了至少一个项，c[k]必须为1。从技术上讲，如果没有从该类中选择任何项，我们还希望强制c[k]必须为0，但我们不需要这样做，因为优化器无论如何都会尝试将c[k]设置为0以满足约束

不管怎样，你先算出这个数学公式，然后找一个整数规划解算器，比如CPLEX或MIPhttps://pypi.org/project/mip/，把问题表达出来，然后帮你解决

如果你想把它变成一个有趣而怪异的项目，试着在D波量子计算机上解决它。他们的免费试用版可能包含足够的comptue功能：D这已经是一个二进制优化问题了，现在你只需要按照他们的教程来处理约束

我试着想动态规划是否可以在这里工作，但也许跟踪已经选择了哪些类会使递归关系变得非常复杂

如果整数规划和量子计算都不能很好地工作，那么可能需要用局部搜索启发法来做一些事情，比如模拟退火

不管怎样，这就是我的想法。也许我把它复杂化了，这里有一个简单的算法解决方案