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

Question

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

algorithmdata-structuresdynamic-programmingsubset-sumclrs

10

给定：整数数组值K，M

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

是否存在非动态规划解决此问题的方法？或者只有dp [i] [j] [k]可以解决这种类型的问题！你能解释一下算法吗。

- Shivendra

我无法理解你的问题，请你能否在这里提供一个例子。这是我所理解的，[3,5,2,6,1,8,15,18,4] 如果 K 是 3，M 是 15，那么我可以选择 8、2、4，这是否是答案？ - AKS

@AKS的问题是...我们只能制作长度为K的子集...在这些长度为K的子集中，哪个子集给出最大的总和...前提是总和小于M。 - Shivendra

好的，根据我所举的例子，如果k为3，则在所有长度为3且总和最大但小于15的子集中。谢谢！ - AKS

这个问题在这里讨论：http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/nanda-scribe-3.pdf - darksky

@darksky 我觉得这不是我所问的。虽然很相似，但并不完全符合我的要求。 - Shivendra

3个回答

1

我们正在寻找一个元素子集，使其元素之和最大，但小于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。

我们可以使用完全相同的方法，因为问题的形式完全相同。缩小后的问题是从values[0] ... values[Z-1]中选取一个子集，使得元素之和最大，但小于M - values[Z]。

一旦我们以同样的方式限制了该值，我们就可以对每个最高值对的第三大值进行限制。等等。

这为我们提供了一棵搜索树结构，希望搜索的组合比N选K少得多。

- John

这是否满足它是一个子集的需求！我认为解决方案就像一个子数组...子集可以是任何子序列！不过我会尝试你的解决方案。 - Shivendra

是的，它确实满足是一个子集合。我对这些元素进行了排序，以便我可以限定该子集中最大元素的值，并满足您的条件。我们不需要使用低于values[X]的任何最大值，因为所有K个元素的子集的最大总和仍小于M。同样，我们也不需要检查任何大于values[Y]的值，因为所有那些具有K个元素的子集的最小总和已经大于M。明白我的意思吗？ - John

0

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包含[0,2,3]，对应于元素1、5、6。

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();
    }
}

- Marc Meketon

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- weeb · Accepted Answer

许多人正确地评论说，下面的答案来自多年前，使用了动态规划，错误地编码解决方案，允许数组元素在“子集”中出现多次。幸运的是，仍然有一种基于DP的方法。

令 dp [i] [j] [k] = true，如果存在一个大小为 k 的子集，其和为输入数组的前 i 个元素之和为 j 。

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

现在，无论是前 i 个元素的大小 k 的子集是否使用了 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的子集，由一个总和超过M的大小为K-1的子集以及另一个足够负面的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的子集，则为true，否则为false。思路是dp [][ ]将编码每个可能长度的所有可能子集的总和。然后，我们可以简单地找到最大的j <= M，使得dp [K] [j]为true。我们的基本情况是dp [0] [0] = true，因为我们始终可以通过选择大小为0的子集来使总和为0。

递归也很简单。假设我们使用数组的前n个值计算了dp [][ ]的值。要查找数组的前n +1 个值的所有可能子集，我们只需取n +1 个值并将其添加到我们之前看到的所有子集中即可。更具体地说，我们有以下代码：

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