K的最大值和小于M的总和。

Given: array of integers value K,M

给定:整数的数组K,M。

Question: Find the maximum sum which we can obtain from all K element subsets of given array such that sum is less than value M?

问题:从给定数组的所有K个元素子集中找到的最大和，这样的和小于M?

is there a non dynamic programming solution available to this problem? or if it is only dp[i][j][k] can only solve this type of problem! can you please explain the algorithm.

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

3 个解决方案

#1

This is a variant of the Knapsack or subset-problem, where in terms of time (at the cost of exponential growing space requirements as the input size grows), dynamic programming is the most efficient method that CORRECTLY solves this problem. See Is this variant of the subset sum problem easier to solve? for a similar question to yours.

这是Knapsack或subset-problem的变体，在时间方面(随着输入规模的增长，以指数增长的空间需求为代价)，动态编程是最有效的解决此问题的方法。看到这个子集和问题的变体更容易解决吗?我想问你一个类似的问题。

However, since your problem is not exactly the same, I'll provide an explanation anyways. Let dp[i][j] = true, if there is a subset of length i that sums to j and false if there isn't. The idea is that dp[][] will encode the sums of all possible subsets for every possible length. We can then simply find the largest j <= M such that dp[K][j] is true. Our base case dp[0][0] = true because we can always make a subset that sums to 0 by picking one of size 0.

不过，既然你的问题不完全一样，我还是会提供解释的。让dp[i][j] = true，如果有一个长度i的子集，如果没有。其思想是，dp[][]将为每一个可能的长度编码所有可能子集的总和。然后我们可以找到最大的j <= M，这样dp[K][j]是正确的。我们的基本情况dp[0][0] = true，因为我们总是可以通过选择0大小的一个子集来将一个子集加到0。

The recurrence is also fairly straightforward. Suppose we've calculated the values of dp[][] using the first n values of the array. To find all possible subsets of the first n+1 values of the array, we can simply take the n+1_th value and add it to all the subsets we've seen before. More concretely, we have the following code:

递归式也很简单。假设我们使用数组的第n个值计算了dp[][]的值。为了找到数组的第一个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

#2

We're looking for a subset of K elements for which the sum of the elements is a maximum, but less than M.

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

We can place bounds [X, Y] on the largest element in the subset as follows.

我们可以在子集的最大元素上设置界限(X, Y)，如下所示。

First we sort the (N) integers, values[0] ... values[N-1], with the element values[0] is the smallest.

首先，我们排序(N)整数，值[0]…值[N-1]，元素值[0]最小。

The lower bound X is the largest integer for which

下界X是最大的整数。

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

值[X]+值(X - 1)+ ....+(X -(k - 1))值< M。

(If X is N-1, then we've found the answer.)

(如果X是N-1，那么我们已经找到了答案。)

The upper bound Y is the largest integer less than N for which

上界Y是小于N的最大整数。

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

值[0]+值[1]+…+值[K-2] +值[Y] < M。

With this observation, we can now bound the second-highest term for each value of the highest term Z, where

通过这个观察，我们现在可以把最高的Z的每个值的第二高的项绑定在这里。

X <= Z <= Y.

X <= Z <= Y。

We can use exactly the same method, since the form of the problem is exactly the same. The reduced problem is finding a subset of K-1 elements, taken from values[0] ... values[Z-1], for which the sum of the elements is a maximum, but less than M - values[Z].

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

Once we've bound that value in the same way, we can put bounds on the third-largest value for each pair of the two highest values. And so on.

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

This gives us a tree structure to search, hopefully with much fewer combinations to search than N choose K.

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

#3

Felix is correct that this is a special case of the knapsack problem. His dynamic programming algorithm takes O(K*M) size and O(K*K*M) amount of time. I believe his use of the variable N really should be K.

费利克斯是正确的，这是一个特殊情况的背包问题。他的动态规划算法采用O(K*M)大小和O(K*K*M)时间。我相信他对变量N的使用应该是K。

There are two books devoted to the knapsack problem. The latest one, by Kellerer, Pferschy and Pisinger [2004, Springer-Verlag, ISBN 3-540-40286-1] gives an improved dynamic programming algorithm on their page 76, Figure 4.2 that takes O(K+M) space and O(KM) time, which is huge reduction compared to the dynamic programming algorithm given by Felix. Note that there is a typo on the book's last line of the algorithm where it should be c-bar := c-bar - w_(r(c-bar)).

有两本关于背包问题的书。最新的一个，由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))。

My C# implementation is below. I cannot say that I have extensively tested it, and I welcome feedback on this. I used BitArray to implement the concept of the sets given in the algorithm in the book. In my code, c is the capacity (which in the original post was called M), and I used w instead of A as the array that holds the weights.

我的c#实现在下面。我不能说我已经对它进行了广泛的测试，我欢迎对此的反馈。我使用了位数组来实现书中算法给出的集合的概念。在我的代码中，c是容量(在原来的post中称为M)，我使用w而不是A作为权重的数组。

An example of its use is:

它使用的一个例子是:

int[] optimal_indexes_for_ssp = new SubsetSumProblem(12, new List<int> { 1, 3, 5, 6 }).SolveSubsetSumProblem();

where the array optimal_indexes_for_ssp contains [0,2,3] corresponding to the elements 1, 5, 6.

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

#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

#2