平衡分区vs背包1/0复杂度

Question

平衡分区：。您有一组n个整数，每个整数在0 ... K范围内。将这些整数分成两个子集，这样可以最小化| S1 - S2 |，其中S1和S2表示两个子集中每个元素的总和。 背包问题：给定一组物品，每个物品都有一个重量和一个值，确定要包括在一个集合中的每个物品的数量，以便总重量小于或等于给定的限制，并且总值是一样大尽可能。不能使用同一个对象两次。

似乎解决平衡分区问题的方法是简单地将背包算法应用于背包S/2的大小，其中S是所有输入数的总和，并且权重等于每个对象。不过，它表示here背包问题是O（nC），而平衡分区问题是O（n^2 k）。我错过了什么？

Answer 1

因为如果每个整数等于k，C可以等于k * n。所以你在这种情况下得到整数背包问题O（k * n^2）的运行时间。