balancer 分区与背包1/0的复杂性

balancer 分区: . 你有一组n个整数,每个都在0 ... K范围内 . 将这些整数划分为两个子集,以便最小化| S1 - S2 |,其中S1和S2表示两个子集中每个子集中元素的总和 . 背包问题:给定一组具有权重和值的项目,确定要包含在集合中的每个项目的数量,以使总权重小于或等于给定限制,并且总值与可能 . 不能两次使用同一个对象 .

似乎 balancer 分区问题的解决方案是简单地应用背包算法,对于背包S / 2的大小,其中S是所有输入数的总和,并且权重等于每个对象的值 . 它仍然说here背包问题是O(nC),而 balancer 分区问题是O(n ^ 2 k) . 我错过了什么?

回答(1)

2 years ago

因为如果每个整数等于k,C可以等于k * n . 因此,在这种情况下,您可以获得整数背包问题的运行时间O(k * n ^ 2) .