有界子集和

Question

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

在一组S = {N1，N2，N3 ... Ni}中，每个元素可以多次选择，上限为{L1，L2，L3 ... Li}。问题是，从S中找到一个子集的最有效算法是什么，即子集总和<= Wi（0 <= Wi）也是最大总和。

这就像一个独立于值的有界背包问题。我知道当所有元素的极限都为1时，可以在伪多项式时间内求解。但是我想知道是否存在伪多项式算法来解决这种变体子集和问题？谢谢！

Answer 1

正如注释中正确指出的那样，可以通过相同的0-1背包算法解决当前的问题，只需创建每种类型的物品数量与允许使用的次数即可。

但是，您引入了不允许这种扭曲的方式，因此让我们考虑这个更普遍的问题：您有一组{N1, N2, ..., Nk}元素，对于每个Ni，您都知道了Li的次数可以选择此元素，但cost函数是任意的f(i, j)，其中i是元素索引，j是我们选择它的次数。 （因此，例如，与原始问题对应的成本函数为f(i, j) = Ni * j。）并且，如果我理解正确，您只是在试图找到低于某个值W的成本函数值的最大可能和。] >

让我们定义一个函数isPossible(i, sum)，该函数回答是否有可能选择第一个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
用英语：如果我们能够通过使用前w个元素获得总和i，我们应该能够使用以下方法获得总和w+f(i, 0)，w+f(i, 1)，...，w+f(i, Li)：前i个元素和Ni一些次数-只要它们都在W下。

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

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