这是一个非多项式问题吗？如果不是，如何在多项式时间内解决？
Is this a non-polynomial problem? If not, how can it be solved in polynomial time?
问题：
Write a function that has 2 input parameters:
items: a list/vector of 2-tuple positive integers (i.e. >= 1)target: a positive integer (i.e. >= 1)
Find a subset of tuples such that:
- The sum of the first tuple elements of the subset is greater than or equal to the input
target.
- The sum of the second tuple elements of the subset is minimal, and let's call that sum value
best.
The function should just return best. Also, it is guaranteed that there is a solution. In other words, the sum of all the first tuple elements is always greater than or equal to the target.
Here is the pseudocode signature of such a function:
(items: List<(int, int)>, target: int) -> int
And here are some examples...
Example A:
- items =
[(25,50), (49,51), (25,50), (1,100)]
- target =
50
- answer =
100
Example B:
- items =
[(25,50), (49,51), (25,50), (1,5)]
- target =
50
- answer =
56
这是我天真的指数时间解决方案：
- 遍历所有可能的子集（因此指数时间）
- 对于每个子集，计算第一个元组元素的总和
- 如果该总和大于或等于目标，则计算第二个元组元素的总和
- 如果新总和是迄今为止找到的最小值，则更新最小值
我还尝试确定是否存在数学 属性 允许使用快捷方式的问题，例如按照最大的“第一元素除以第二元素”比率浏览项目（最物有所值）。但是，如示例 A 所示，这并非对所有情况都有效。
这是一个非多项式问题吗？如果不是，如何在多项式时间内解决？
这是一个 0-1 背包问题：https://en.wikipedia.org/wiki/Knapsack_problem
元组是物品，第一个元组元素是物品值，第二个元组元素是物品权重。经典背包问“best 小于某个特定限制。
因此，这个问题是 NP 完全问题，没有多项式时间解。
正常的动态规划解决方案可以适应 O(items.length * 最佳)。最简单的方法就是使用普通的DP方法，先对best做一个小的limit，然后加倍直到达到目标值。
问题：
Write a function that has 2 input parameters:
items: a list/vector of 2-tuple positive integers (i.e. >= 1)target: a positive integer (i.e. >= 1)Find a subset of tuples such that:
- The sum of the first tuple elements of the subset is greater than or equal to the input
target.- The sum of the second tuple elements of the subset is minimal, and let's call that sum value
best.The function should just return
best. Also, it is guaranteed that there is a solution. In other words, the sum of all the first tuple elements is always greater than or equal to the target.Here is the pseudocode signature of such a function:
(items: List<(int, int)>, target: int) -> intAnd here are some examples...
Example A:
- items =
[(25,50), (49,51), (25,50), (1,100)]- target =
50- answer =
100Example B:
- items =
[(25,50), (49,51), (25,50), (1,5)]- target =
50- answer =
56
这是我天真的指数时间解决方案：
- 遍历所有可能的子集（因此指数时间）
- 对于每个子集，计算第一个元组元素的总和
- 如果该总和大于或等于目标，则计算第二个元组元素的总和
- 如果新总和是迄今为止找到的最小值，则更新最小值
我还尝试确定是否存在数学 属性 允许使用快捷方式的问题，例如按照最大的“第一元素除以第二元素”比率浏览项目（最物有所值）。但是，如示例 A 所示，这并非对所有情况都有效。
这是一个非多项式问题吗？如果不是，如何在多项式时间内解决？
这是一个 0-1 背包问题：https://en.wikipedia.org/wiki/Knapsack_problem
元组是物品，第一个元组元素是物品值，第二个元组元素是物品权重。经典背包问“best 小于某个特定限制。
因此，这个问题是 NP 完全问题，没有多项式时间解。
正常的动态规划解决方案可以适应 O(items.length * 最佳)。最简单的方法就是使用普通的DP方法，先对best做一个小的limit，然后加倍直到达到目标值。