问题：
编写一个具有2个输入参数的函数：
items：2元组正整数的列表/向量(即>=1(target：正整数(即>=1(找到元组的子集，这样：
- 子集的第一元组元素的和大于或等于输入
target- 子集的第二个元组元素的和是minimal，让我们将该和值称为
best函数应该只返回
best。此外，可以保证有一个解决方案。换句话说，所有第一元组元素的和总是大于或等于目标。这是这样一个函数的伪代码签名：
(items: List<(int, int)>, target: int) -> int下面是一些例子。。。
示例A:
- 项目=
[(25,50), (49,51), (25,50), (1,100)]- 目标=
50- 答案=
100示例B:
- 项目=
[(25,50), (49,51), (25,50), (1,5)]- 目标=
50- 答案=
56
这是我天真的指数时间解决方案：
- 遍历所有可能的子集(因此是指数时间(
- 对于每个子集，计算第一个元组元素的和
- 如果该和大于或等于目标，则计算第二元组元素的和
- 如果新的总和是迄今为止发现的最小值，请更新最小值
我还试图确定问题是否存在允许快捷方式的数学性质，例如通过最大的"；第一元素除以第二元素"；比例(物超所值(。然而，如示例A所示，这并不是对所有情况都有效。
这是一个非多项式问题吗？如果不是，如何在多项式时间内求解？
这是一个0-1背包问题：https://en.wikipedia.org/wiki/Knapsack_problem
元组是项，第一元组元素是项值，第二元组元素是项目权重。经典的背包要求"；是CCD_ 12小于某个特定限制。
因此，这个问题是NP完全的，并且没有多项式时间解。
正常的动态编程解决方案可以适用于O(items.length*best(。最简单的方法是使用正常的DP方法，首先对最佳值进行一个小的限制，然后将其加倍，直到达到目标值。