大小为K的子集的总和小于M

Question

给出：整数数组值K，M

问题：找到我们可以从给定数组的所有K个元素子集中获得的最大和，以使该和小于值M？

是否有非动态编程解决方案可用于此问题？或者仅是dp [i] [j] [k]可以解决这类问题！能否请您解释一下算法。

Answer 1

[许多人正确地评论说，几年前使用动态编程的答案不正确地编码了解决方案，从而使数组的元素多次出现在“子集中”。幸运的是，仍然有希望采用基于DP的方法。

让dp[i][j][k] = true，如果输入数组的前k个元素中存在一个大小为i的子集，总计为j

我们的基本情况是dp[0][0][0] = true

现在，第一个k元素的大小i子集使用a[i + 1]，否则不使用，请重复执行

dp[i + 1][j][k] = dp[i][j - a[i + 1]][k - 1] OR dp[i][j][k]

将所有内容放在一起：

given A[1...N]
initialize dp[0...N][0...M][0...K] to false
dp[0][0][0] = true
for i = 0 to N - 1:
    for j = 0 to M:
        for k = 0 to K:
            if dp[i][j][k]:
                dp[i + 1][j][k] = true
            if j >= A[i] and k >= 1 and dp[i][j - A[i + 1]][k - 1]:
                dp[i + 1][j][k] = true
max_sum = 0
for j = 0 to M:
    if dp[N][j][K]:
        max_sum = j
return max_sum

给出O(NMK)的时间和空间复杂度。

退一步，我们在这里隐式地做出了一个假设，即A[1...i]都是非负的。如果为负数，则初始化第二维0...M是不正确的。考虑由总和超过K的大小K - 1子集和M的另一个足够负的元素组成的大小A[]子集，使得总和不再超过M。类似地，我们的大小K - 1子集可以加和为一个非常负的数，然后将A[]的足够正数元素加和为M。为了使我们的算法在两种情况下仍然有效，我们需要将第二维从M增加到A[]中所有正元素的总和与所有负元素的总和之间的差（绝对值之和A[]中所有元素的值）。

关于是否存在非动态编程解决方案，当然存在天真的指数时间蛮力解决方案和可优化指数常数因子的变量。]​​>

除此之外？那么，您的问题与子集总和密切相关，并且关于NP大问题的完整文献也很多。而且由于一般原理的算法可以有各种形状和大小-我想像做这样的事是不可能的：随机化，近似化（只需选择误差参数要足够小！）其他NP完全问题的普通旧约简（将您的问题转换成巨大的布尔电路并运行SAT解算器）。是的，这些是不同的算法。它们比动态编程解决方案快吗？其中一些可能。它们是否简单易懂或易于实施，无需对算法材料进行标准介绍之外的培训？可能不是。

这是背包问题或子集问题的一种变体，在时间上（随着输入大小的增长，以成倍的空间需求为代价），动态编程是正确解决此问题的最有效方法。有关与您类似的问题，请参见Is this variant of the subset sum problem easier to solve?。

但是，由于您的问题并不完全相同，因此无论如何我都会提供一个解释。令dp[i][j] = true，如果存在长度为i的子集总计为j，则为false。这个想法是dp[][]将对每个可能的长度编码所有可能的子集的总和。然后，我们可以简单地找到最大的j <= M，使dp[K][j]为true。我们的基本情况dp[0][0] = true，因为我们总是可以通过选择大小为0的一个来制作一个总和为0的子集。

重复也相当简单。假设我们已经使用数组的前dp[][]个值计算了n的值。要查找数组的第一个n+1值的所有可能子集，我们可以简单地将n+1 _th值添加到我们之前看到的所有子集中。更具体地说，我们有以下代码：

initialize dp[0..K][0..M] to false
dp[0][0] = true
for i = 0 to N:
    for s = 0 to K - 1:
        for j = M to 0:
            if dp[s][j] && A[i] + j < M:
                dp[s + 1][j + A[i]] = true
for j = M to 0:
    if dp[K][j]:
        print j
        break

我们正在寻找K个元素的子集，其元素之和最大，但小于M。

我们可以如下将边界[X, Y]放在子集中的最大元素上。

首先，我们对（N）个整数values[0] ... values[N-1]进行排序，其中元素values[0]最小。

下界X是其最大整数

values[X] + values[X-1] + .... + values[X-(K-1)] < M。

（（如果X为N-1，那么我们找到了答案。）

上限Y是小于N的最大整数

values[0] + values[1] + ... + values[K-2] + values[Y] < M。

有了这个观察，我们现在可以将第二高的项绑定到最高项Z的每个值，其中

X <= Z <= Y。

我们可以使用完全相同的方法，因为问题的形式完全相同。减少的问题是找到K-1个元素的子集，该子集取自values[0] ... values[Z-1]，其元素之和为最大值，但小于M - values[Z]。

一旦我们以相同的方式绑定了that

值，就可以为两个最高值中的每对值的第三大值设置边界。依此类推。

[这为我们提供了一个要搜索的树结构，希望搜索的组合要少于N选择K。

Felix是正确的，这是背包问题的特例。他的动态编程算法占用O

（K * M）的大小和O

（K * K * M）的时间。我相信他对变量N的使用确实应该是K。

有两本专门讨论背包问题的书。 Kellerer，Pferschy和Pisinger的最新文章[2004，Springer-Verlag，ISBN 3-540-40286-1]在他们的第76页图4.2上给出了一种改进的动态编程算法，该算法采用O（K + M ）空间和O

（KM）时间，与Felix提供的动态编程算法相比，这是巨大的减少。请注意，该书的算法最后一行上有一个错字，应该是c-bar：= c-bar-w_（r（c-bar））。

我的C＃实现如下。我不能说我已经对其进行了广泛的测试，欢迎对此提出反馈。我用BitArray实现了书中算法中给出的集合的概念。在我的代码中，c是容量（在原始文章中称为M），我用w而不是A作为保存权重的数组。

其使用示例是：

int[] optimal_indexes_for_ssp = new SubsetSumProblem(12, new List<int> { 1, 3, 5, 6 }).SolveSubsetSumProblem();
其中数组optimal_indexes_for_ssp包含与元素1、5、6对应的[0,2,3]。
using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;

public class SubsetSumProblem
{
    private int[] w;
    private int c;

    public SubsetSumProblem(int c, IEnumerable<int> w)
    {
      if (c < 0) throw new ArgumentOutOfRangeException("Capacity for subset sum problem must be at least 0, but input was: " + c.ToString());
      int n = w.Count();
      this.w = new int[n];
      this.c = c;
      IEnumerator<int> pwi = w.GetEnumerator();
      pwi.MoveNext();
      for (int i = 0; i < n; i++, pwi.MoveNext())
        this.w[i] = pwi.Current;
    }

    public int[] SolveSubsetSumProblem()
    {
      int n = w.Length;
      int[] r = new int[c+1];
      BitArray R = new BitArray(c+1);
      R[0] = true;
      BitArray Rp = new BitArray(c+1);
      for (int d =0; d<=c ; d++) r[d] = 0;
      for (int j = 0; j < n; j++)
      {
        Rp.SetAll(false);
        for (int k = 0; k <= c; k++)
          if (R[k] && k + w[j] <= c) Rp[k + w[j]] = true;
        for (int k = w[j]; k <= c; k++) // since Rp[k]=false for k<w[j]
          if (Rp[k])
          {
            if (!R[k]) r[k] = j;
            R[k] = true;
          }
      }
      int capacity_used= 0;
      for(int d=c; d>=0; d--)
        if (R[d])
        {
          capacity_used = d;
          break;
        }
      List<int> result = new List<int>();
      while (capacity_used > 0)
      {
        result.Add(r[capacity_used]);
        capacity_used -= w[r[capacity_used]];
      } ;
      if (capacity_used < 0) throw new Exception("Subset sum program has an internal logic error");
      return result.ToArray();
    }
}

Answer 2

我们正在寻找K个元素的子集，其元素之和最大，但小于M。

Answer 3

Felix是正确的，这是背包问题的特例。他的动态编程算法占用O