sorting - 在权重约束下最大化整数条目的总和

Question

我有一个整数数组。让我们用 A 来表示它。还有另一个数组 W 包含与 A 的每个条目相关联的权重。

换言之，与每个条目A[i]相关联的是某个权重条目W[i]。（请注意，权重超出了有限的集合 S_w = {w1,w2,w3,w4} 所以只有少数可能的值）

问题陈述如下：从 A 中选择一个随机数的条目，这样当它们相加时，在它们各自的权重之和 (SUM_W) 不超过阈值的约束下，给你最高值 (SUM_A)， W_阈值。

一种可能性是蛮力：计算 A 的所有排列，对于每个排列，选择前 n 个条目，使得它们的总权重 SUM_W 不超过 W_threshold。最后，应选择给出最大 SUM_A 的排列。但是由于 A 的长度不受限制，由于置换计算步骤，该方案的复杂性非常高。

另一种（次优）可能性是按降序对 A 进行排序，然后选择前 n 个条目，使其 SUM_W 不超过 W_threshold。这具有较低的复杂性，但结果将是次优的。

如果他们已经存在解决上述问题的算法，有人可以给我提示吗？或者，如果有人有比我上面描述的更好的想法。非常感谢

标签： sortingtreeconstraintsmaxgraph-algorithm