10

给定：整数数组 K,M

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

这个问题有可用的非动态编程解决方案吗？或者如果只有 dp[i][j][k] 只能解决这类问题！你能解释一下算法吗？

4

3 回答 3

8

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

dp[i][j][k]如果存在输入数组k的第一个元素的大小子集，则令= trueij

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

现在，要么第一个元素的大小k子集使用，要么不使用，给出递归ia[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[]sum to元素M。为了让我们的算法在这两种情况下仍然有效，我们需要将第二维从M增加到中所有正元素之和之间的差A[]和所有负元素之和（ 中所有元素的绝对值之和A[]）。

至于是否存在非动态规划解决方案，当然有朴素的指数时间蛮力解决方案和优化指数中的常数因子的变化。

除此之外？好吧，您的问题与子集和密切相关，而且大名鼎鼎的 NP 完全问题的文献相当广泛。作为一般原则，算法可以有各种形状和大小——我不能想象说，随机化，近似，（只需选择足够小的误差参数！）对其他 NP 完全问题的简单旧约化（将您的问题转换为巨大的布尔电路并运行 SAT 求解器）。是的，这些是不同的算法。它们比动态编程解决方案更快吗？其中一些，可能。它们是否易于理解或实施，无需说超出标准介绍算法材料的培训？可能不是。

这是背包问题或子集问题的变体，在时间方面（以随着输入大小的增长而呈指数增长的空间需求为代价），动态规划是正确解决此问题的最有效方法。请参阅子集和问题的这个变体更容易解决吗？对于与您类似的问题。

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

复发也相当简单。假设我们已经使用数组dp[][]的第一个值计算了值。要找到数组第一个值的n所有可能子集，我们可以简单地取第_th 个值并将其添加到我们之前见过的所有子集中。更具体地说，我们有以下代码：n+1n+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

于 2013-08-06T13:57:57.707 回答
1

我们正在寻找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]。

一旦我们以相同的方式限制了该值，我们就可以为两个最大值中的每一对设置第三大值。等等。

这给了我们一个树形结构来搜索，希望搜索的组合比 N 选择 K 少得多。

于 2013-08-05T22:36:24.103 回答
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包含对应于元素 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();
    }
}
于 2013-08-30T14:26:58.490 回答