balancer 分区： . 你有一组n个整数，每个都在0 ... K范围内 . 将这些整数划分为两个子集，以便最小化| S1 - S2 |，其中S1和S2表示两个子集中每个子集中元素的总和 . 背包问题：给定一组具有权重和值的项目，确定要包含在集合中的每个项目的数量，以使总权重小于或等于给定限制，并且总值与可能 . 不能两次使用同一个对象 .
似乎 balancer 分区问题的解决方案是简单地应用背包算法，对于背包S / 2的大小，其中S是所有输入数的总和，并且权重等于每个对象的值 . 它仍然说here背包问题是O（nC），而 balancer 分区问题是O（n ^ 2 k） . 我错过了什么？
1 回答
因为如果每个整数等于k，C可以等于k * n . 因此，在这种情况下，您可以获得整数背包问题的运行时间O（k * n ^ 2） .