有界子集和

Question

我有一个关于变体子集和问题的问题。

在集合S = {N1, N2, N3...Ni}中，每个元素可以多次选择，上限= { L1、L2、L3……李}。问题是，从 S 中找到一个子集的最有效算法是什么，使得子集总和 <= Wi (0 <= Wi) 并且它也是最大总和。

这就像一个与价值无关的有界背包问题。我知道当所有元素的极限都为1时，可以用伪多项式时间求解。但我想知道是否有针对这种变体子集和问题的伪多项式算法？谢谢！

Answer 1

正如评论中正确指出的那样，目前的问题可以通过相同的 0-1 背包算法来解决，只需创建与允许使用它的次数一样多的每种类型的项目.

但是，你引入了一个不允许这样做的扭曲，所以让我们考虑这个更普遍的问题：你有一组 {N1, N2, ..., Nk} 个元素，并且对于每个 Ni 你知道 Li 你可以 select 这个元素，但是成本函数是任意的 f(i, j)，其中 i 是元素索引， j 是我们 select编辑它。（因此，例如，与原始问题相对应的成本函数是 f(i, j) = Ni * j）而且，如果我理解正确的话，您只是在尝试找到低于某个值 [=18] 的成本函数值的最大可能总和=].

让我们定义一个函数 isPossible(i, sum) 来回答是否可以 select 前 i 个元素的某种组合（每个元素最多被允许多次）并达到总和sum。初始值为isPossible(0, 0) = True, isPossible(0, s>0) = False：通过使用前0个元素（即根本没有元素），我们只能得到和0.

现在让我们按照索引的递增顺序遍历元素，并遍历我们要使用特定元素的次数，并相应地更新 isPossible 中的值：

for i in 0..k-1:
  for j in 0..Li:
    for w in 0..W - f(i, j):
      if isPossible[i][w]:
        isPossible[i+1][w + f(i, j)] = True

英文：如果我们能够通过使用前i个元素获得和w，我们应该能够获得和w+f(i, 0)，w+f(i, 1), ..., w+f(i, Li) 使用第一个 i 元素和 Ni 一些次数 - 只要它们都属于 W.

（请注意，如果成本函数可以具有负值，则算法需要进行一些调整 - 我们不能再假设允许的中间和的范围是 [0, W]。）

这显然仍然是伪多项式，但它比通常的背包小得多，因为我们必须迭代我们使用每个项目的次数。

有界子集和

Bounded subset sum

algorithm

dynamic-programming

knapsack-problem

subset-sum