动态规划求和

Question

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

在思考这个问题时，我有些困惑。

- CyberShot

---

总和可以大于或小于K，只是不能相等？ - Vaughn Cato

@vaughncato 是的，它必须尽可能接近 K。 - Óscar López

@VaughnCato：你是不是应该说“不仅仅”而不是“仅仅不”? - Undreren

@Undreren：我想我应该说“bot不等于”。 - Vaughn Cato

Answer 1

通常的表述是你要找到最接近但不超过K的值。如果你的意思是“小于K”，那么你的K值比通常的值大1。如果你真正的意思只是“不等于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&1]和table[(i-1)&1]分别替换table[i]和table[i-1]（仅适用于主表，不适用于访问used表时）。

- Jerry Coffin

Answer 2

以下是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]

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

- Vaughn Cato

Answer 3

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

- soegaard