python-3.x - 等和组合(类似于子集和和换币算法)

Question

我有换硬币问题，除了扭曲:不是从无限硬币中找到等于单个总和的解决方案，而是从一组有限的硬币中找到小于的解决方案列表总和的集合。

(经典问题的一个很好的链接是 here )

(这也类似于子集和问题，除了一组目标而不是一个 - 链接 here )

一个类似但不同且似乎更难编码的问题:

给定-

• 可能的数值列表，必须全部使用 [1, 9, 4, 1, 3, 2]
• 可达到的最大总数的组列表 [(GroupA,17), (GroupB,1), (GroupC,5)]

目标 - 将列表中的每个数值分配给一个组，以便所有项目都使用以下约束:每个组的值的总和不得超过分配的最大值。

例如，这个例子可能会找到 3 个解决方案:

[[GroupA,[9,4,1,3]], [GroupB, [1]], [GroupC, [2]],
[GroupA,[9,4,1,2]], [GroupB, [1]], [GroupC, [3]],
[GroupA,[9,2,1,3]], [GroupB, [1]], [GroupC, [4]]]

Answer 1

这称为多背包问题。您有 n 个元素，重量为 w[i]，m 个背包，容量为 c[i]，并且您需要将元素分配给背包，以便没有元素超出其容量。

Wikipedia提供问题的整数规划公式，这就是我解决实际示例所采用的方法 - 通过使用 IP 求解器。

为了完整起见，IP 公式为:

maximize sum(x[i,j] * w[j], i=1..m, j=1..n)
such that:
sum(x[i,j], i=1..m) <= 1 (for all j=1..n)
sum(x[i,j] * w[j], j=1..n) < c[i]  (for all i=1..m)
x[i][j] = 0 or 1 (for all i=1..m, j=1..n)

也就是说，您正在最大化背包中元素的总重量，这样一来，没有元素被分配到一个以上的背包中，没有背包超过其容量，并且元素是离散的(它们不能部分分配给一个背包)。这被表述为一个优化问题——但当然，您可以查看最佳解决方案，看看它是否分配了所有项目。