在一次招聘会上,我被问到以下棘手的问题(不完全是下面的,我剥离了这个故事并(或多或少)正式地表达了这个问题)。
Given number
K
, and a finite list of pairsL = < (a,b), (c,d), (e,f) >
where each pairp
consists of two numbersn1
andn2
. Find the the listR
where the sum of then1
values of all its pairs is the greatest and the sum of all then2
values of its pairs is less than or equal toK
. In the listR
, 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
.
有更好的方法吗?
最佳答案
这就是“无界背包问题”。它是 NP 难的,所以没有(已知的)多项式解,但是如果 n2 和 K 是整数,则有一个已知的伪多项式时间解,您可以在这里找到:https://en.wikipedia.org/wiki/Knapsack_problem#Solving
上面描述的动态规划解决方案,是计算,对于每个容量k,0<=k<=K,对于列表L
的每个前缀,sum(n1 ) 这样 sum(n2)<=k.
关于algorithm - 动态规划 : Maximizing,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49807698/