algorithm - 动态规划 : Maximizing

Question

在一次招聘会上，我被问到以下棘手的问题(不完全是下面的，我剥离了这个故事并(或多或少)正式地表达了这个问题)。

Given number K, and a finite list of pairs L = < (a,b), (c,d),
(e,f) > where each pair p consists of two numbers n1 and n2. Find the the list R where the sum of the n1 values of all its pairs is the greatest and the sum of all the n2 values of its pairs is less than or equal to K. In the list R, pairs can repeat.

例如，如果您的 K是 10，你有对列表 L作为<(3,2) , (1,7), (4,6) > , 那么结果就是 R = < (3,2), (3,2), (3,2), (3,2), (3,2) >所以所有n1的总和值为 3 + 3 + 3 + 3 + 3 = 15和所有 n2 的总和值为 2 + 2 + 2 + 2 + 2 = 10 .这将是正确的解决方案，而不是像 <(3,2), (3,2), (4,6)> 这样的解决方案。 (n1 总和为 10；n2 总和为 10)或类似 <(1,7), (3,2)> (n1 总和为 4；n2 总和为 9)其n1总和不是可能的最大值。

我描述了一种方法，我基本上会枚举所有可能的对组合，其 n2 值总和小于或等于 K。并选择最高 n1 的组合和。可以通过从 K 中递减来完成枚举。 , 每个n2给定列表中对的值 L .

有更好的方法吗？

Answer 1

这就是“无界背包问题”。它是 NP 难的，所以没有(已知的)多项式解，但是如果 n2 和 K 是整数，则有一个已知的伪多项式时间解，您可以在这里找到:https://en.wikipedia.org/wiki/Knapsack_problem#Solving

上面描述的动态规划解决方案，是计算，对于每个容量k，0<=k<=K，对于列表L的每个前缀，sum(n1 ) 这样 sum(n2)<=k.