动态编程总和

Question

你将如何使用动态编程来找到一个数组中的正整数列表,其总和最接近但不等于某个正整数K？

我有点卡住这个想法.

Answer 1

通常的措辞就是你正在寻找最接近但不超过K的值.如果你的意思是"小于K",那就意味着你的K值比通常的值大1.如果你真的只是意味着"不等于K",那么你基本上会经历算法两次,一旦找到小于K的最大和,然后再次找到大于K的最小和,然后选择那些绝对的那个与K的差异是最小的.

目前我假设你真的是指小于或等于K的最大总和,因为这是最常见的公式,其他可能性对算法没有太大影响.

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

然后我们开始遍历表格,并为每个可能的最大值建立最佳值,直到实际最大值,逐行,所以我们只从一个输入开始,然后是两个可能的输入,然后是三个,依此类推.在表中的每个点,只有两种可能的最佳值:不使用当前输入的先前最佳值,或者当前输入加上最大值的前一个最佳值减去当前输入(以及我们按顺序计算表值,我们总是已经有了这个值.

我们通常还想跟踪实际用于生成结果的项目.为此,我们将表中给定点的布尔值设置为true,当且仅当我们使用该行的新输入计算表中该点的值时(而不是仅复制前一行的最佳值).最好的结果是在右下角,所以我们从那里开始,一次一行地向后走过桌子.当我们到达该列的布尔值设置为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).

其次,在表本身中,我们在任何给定时间只使用两行:一行当前行和一行.在此之前,该行(在主表)不被再次使用(即计算行[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表进行处理时.