在一次招聘会上，我被问到了下面这个棘手的问题（不完全是下面的问题，我脱掉了故事，正式地表达了这个问题（或多或少）。
给定的数和一个有限的对列表，其中每个对由两个数组成。
查找列表K，其中
pairs是其pairs的所有L = < (a,b), (c,d), (e,f) >值之和的最大值
小于或等于p在列表n1中，可以重复对。
例如，如果n2是10，并且有一个R对列表，那么结果将是n1，因此所有n2值的总和将是K，所有R值的总和将是K这将是正确的解决方案，而不是像L（<(3,2) , (1,7), (4,6) >总和为10；R = < (3,2), (3,2), (3,2), (3,2), (3,2) >和是10）或类似n1（3 + 3 + 3 + 3 + 3 = 15总和为4；n2和是9），其n2和不是最大可能。
我描述了一种方法，在这种方法中，我将基本上枚举所有可能的成对组合，其n2值的总和将小于或等于2 + 2 + 2 + 2 + 2 = 10个数，并选择具有最高<(3,2), (3,2), (4,6)>和的组合枚举可以通过从n1中递增减去，从给定列表n2中的对中减去每个<(1,7), (3,2)>值来完成。
有更好的办法吗？
最佳答案
这就是“无界背包问题”这是np难的，所以没有（已知的）多项式解，但是如果n2和k是整数，就有一个已知的伪多项式时间解，你可以在这里找到：https://en.wikipedia.org/wiki/Knapsack_problem#Solving
上面描述的动态规划解决方案是，对于每个容量k，0L的每个前缀，计算sum（n1）的最大值，使得sum（n2）
关于algorithm - 动态编程:最大化，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49807698/