5

您将如何使用动态规划来查找数组中的正整数列表，其总和最接近但不等于某个正整数 K？

我对这个有点卡住了。

4

3 回答 3

6

通常的措辞是您正在寻找最接近但不超过 K 的值。如果您的意思是“小于 K”，它只是意味着您的 K 值比通常的值大一。如果你的意思是“不等于 K”，那么你基本上会运行两次算法，一次找到小于 K 的最大和，然后再次找到大于 K 的最小和，然后选择绝对值与 K 的差异最小。

目前我将假设您的意思是小于或等于 K 的最大总和，因为这是最常见的公式，而其他可能性对算法并没有太大影响。

基本思想相当简单，尽管它（至少可能）使用了大量存储空间。我们构建了一个包含 K+1 列和 N+1 行的表（其中 N = 输入数）。我们将表中的第一行初始化为 0。

然后我们开始遍历表格，并为每个可能的最大值建立最佳值，直到真正的最大值，逐行进行，所以我们只从一个输入开始，然后是两个可能的输入，然后是三个，依此类推. 在表中的每个位置，最佳值只有两种可能性：不使用当前输入的前一个最佳值，或者当前输入加上前一个最大值减去当前输入的最佳值（并且因为我们按顺序计算表值，我们总是已经有了那个值）。

我们通常还希望跟踪实际使用哪些项目来产生结果。为此，我们将表中给定点的布尔值设置为真，当且仅当我们使用该行的新输入计算表中该点的值（而不是仅仅复制前一行的最佳值）。最好的结果是在右下角，所以我们从那里开始，然后一次在桌子上向后走一排。当我们到达该列的布尔值设置为 true 的行时，我们知道我们找到了一个使用的输入。我们打印出该项目，然后从总数中减去该项目，以获得左侧的下一列，我们将在其中找到用于产生此输出的下一个输入。

这是一个技术上使用 C++ 的实现，但主要以类似 C 的风格编写，以使每个步骤尽可能明确。

#include <iostream>
#include <functional>

#define elements(array) (sizeof(array)/sizeof(array[0]))

int main() {

    // Since we're assuming subscripts from 1..N, I've inserted a dummy value
    // for v[0].
    int v[] = {0, 7, 15, 2, 1};

    // For the moment I'm assuming a maximum <= MAX.
    const int MAX = 17;

    // ... but if you want to specify K as the question implies, where sum<K, 
    // you can get rid of MAX and just specify K directly:
    const int K = MAX + 1;

    const int rows = elements(v);

    int table[rows][K] = {0};
    bool used[rows][K] = {false};

    for (int i=1; i<rows; i++)
        for (int c = 0; c<K; c++) {
            int prev_val = table[i-1][c];
            int new_val;

            // we compute new_val inside the if statement so we won't 
            // accidentally try to use a negative column from the table if v[i]>c
            if (v[i] <= c && (new_val=v[i]+table[i-1][c-v[i]]) > prev_val) {
                table[i][c] = new_val;
                used[i][c] = true;
            }
            else
                table[i][c] = prev_val;
        }

    std::cout << "Result: " << table[rows-1][MAX] << "\n";
    std::cout << "Used items where:\n";
    int column = MAX;
    for (int i=rows; i>-1; i--)
        if (used[i][column]) {
            std::cout << "\tv[" << i << "] = " << v[i] << "\n";
            column -= v[i];
        }

    return 0;
}

您通常会对此进行一些优化（为了便于阅读，我没有这样做）。首先，如果达到最佳总和，则可以停止搜索，因此在这种情况下，我们实际上可以在考虑最终输入之前跳出循环1（因为15并2给出所需的结果17）。

其次，在表格本身中，我们在任何给定时间实际上只使用两行：一个当前行和一个前一行。之前的行（在主表中）不再使用（即，计算 row[n] 我们需要来自 的值row[n-1]，但不需要row[n-2], row[n-3], ... row[0]。为了减少存储，我们可以使主表只有两个行，然后我们在第一行和第二行之间交换。一个非常类似于 C 的技巧是只使用行号的最低有效位，所以你可以分别用和替换table[i]和（但仅用于主表 - 不是在寻址表时。table[i-1]table[i&1]table[(i-1)&1]used

于 2012-05-14T07:40:14.680 回答
3

这是python中的一个例子：

def closestSum(a,k):
  s={0:[]}
  for x in a:
    ns=dict(s)
    for j in s:
      ns[j+x]=s[j]+[x]
    s=ns
  if k in s:
    del s[k]
  return s[min(s,key=lambda i:abs(i-k))]

例子：

>>> print closestSum([1,2,5,6],10)
[1, 2, 6]

这个想法只是为了跟踪在遍历数组时可以从所有先前的元素中得出什么总和，以及一种得出总和的方法。最后，您只需选择最接近您想要的东西。它是一种动态规划解决方案，因为它将整个问题分解为子问题，并使用表格来记住子问题的结果，而不是重新计算它们。

于 2012-05-14T05:04:53.743 回答
1

Cato 在 Racket 中的想法：

#lang racket
(define (closest-sum xs k)
  (define h (make-hash '([0 . ()])))
  (for* ([x xs] [(s ys) (hash-copy h)])
    (hash-set! h (+ x s) (cons x ys))
    (hash-set! h x (list x)))
  (when (hash-ref h k #f) (hash-remove! h k))
  (cdr (argmin (λ (a) (abs (- k (car a)))) (hash->list h))))

要获得更简洁的程序，可以从 GitHub 获取terse-hash.rkt并编写：

(define (closest-sum xs k)
  (define h {make '([0 . ()])})
  (for* ([x xs] [(s ys) {copy h}])
    {! h (+ x s) (cons x ys)}
    {! h x (list x)})
  (when {h k #f} {remove! h k})
  (cdr (argmin (λ (a) (abs (- k (car a)))) {->list h})))
于 2012-05-15T14:34:56.973 回答