动态规划总和 [英] Dynamic programming sum

问题描述

你会如何使用动态规划找到一个数组，其总和正整数的名单最接近但不等于一定正整数k？

How would you use dynamic programming to find the list of positive integers in an array whose sum is closest to but not equal to some positive integer K?

我对这个有点卡住的思考。

I'm a little stuck thinking about this.

推荐答案

通常的措辞就在于你正在寻找最接近的数值，但不超过K.如果你的意思是小于K，它只是意味着你的K值是比通常的大一个。如果你真正的意思只是不等于K，那么你基本上是通过算法运行两次，第一次发现最大的一笔少于K，然后再次寻找最小和于K越大，然后挑选那些其绝对之一给K差异是最小的。

The usual phrasing for this is that you're looking for the value closest to, but not exceeding K. If you mean "less than K", it just means that your value of K is one greater than the usual. If you truly mean just "not equal to K", then you'd basically run through the algorithm twice, once finding the largest sum less than K, then again finding the smallest sum greater than K, then picking the one of those whose absolute difference from K is the smallest.

有关的那一刻我会假设你真的是最大的总和大于或等于K时，因为这是最常见的提法，而其他的可能性并不真正对算法多影响。

For the moment I'm going to assume you really mean the largest sum less than or equal to K, since that's the most common formulation, and the other possibilities don't really have much affect on the algorithm.

的基本思想是相当简单的，但它（至少潜在地）使用了大量的存储空间。我们建立与K + 1列和N + 1行的表（其中N =输入数量）。我们初始化在表中的第一行到0。

The basic idea is fairly simple, though it (at least potentially) uses a lot of storage. We build a table with K+1 columns and N+1 rows (where N = number of inputs). We initialize the first row in the table to 0's.

然后，我们开始通过该表走，建设最好的价值，我们可以为每个可能的最大值达到了真正的最大值，再逐行所以我们开始只有一个单一的输入，则有两种可能的输入，然后三，等等。在表中的每个点，只有两个最佳值可能：previous最佳值，不使用的电流输入，否则当前输入加上previous最值的最大值减当前输入（因为我们计算表中的值，从而，我们总是已经有值）。

Then we start walking through the table, and building the best value we can for each possible maximum value up to the real maximum, going row by row so we start with only a single input, then two possible inputs, then three, and so on. At each spot in the table, there are only two possibilities for the best value: the previous best value that doesn't use the current input, or else the current input plus the previous best value for the maximum minus the current input (and since we compute the table values in order, we'll always already have that value).

我们还通常希望跟踪哪些项目被实际使用，以产生结果。为了做到这一点，我们在表中设置一个布尔对于给定的点为真当且仅当我们计算了使用新的输入该行（而不仅仅是复制在表中当场价值previous行的最好值）。最好的结果是在底部，右上角，所以我们开始在那里，向后走通过表中的一行的时间。当我们到了一排，其中布尔该列设置为true，我们知道我们发现使用该输入。我们打​​印出的项目，然后减去从总以获得下一列到左侧，我们会发现这是用于生产本输出的下一个输入。

We also usually want to keep track of which items were actually used to produce the result. To do that, we set a Boolean for a given spot in the table to true if and only if we compute a value for that spot in the table using the new input for that row (rather than just copying the previous row's best value). The best result is in the bottom, right-hand corner, so we start there, and walk backward through the table one row at a time. When we get to a row where the Boolean for that column was set to true, we know we found an input that was used. We print out that item, and then subtract that from the total to get the next column to the left where we'll find the next input that was used to produce this output.

下面是一个实现，在技术上在C ++中，但主要是在C-般的风格写尽每一步都尽可能明确。

Here's an implementation that's technically in C++, but written primarily in a C-like style to make each step as explicit as possible.

#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 ）。

There are a couple of things you'd normally optimize in this (that I haven't for the sake of readability). First, if you reach an optimum sum, you can stop searching, so in this case we could actually break out of the loop before considering the final input of 1 at all (since 15 and 2 give the desired result of 17).

其次，在表本身，我们只真正使用两排，在任何给定的时间：1当前行和一个previous行。在此之前，该行（在主表）将永远不会再次使用（例如，计算行[N]，我们需要从数值行[N-1] ，但不行[N-2] ，行[N-3] ... 行[0] 为了减少存储，就可以使在主台只有两行，这样我们交换第一和第二行之间。一个非常类似于C特技这样做将是仅使用行号的最低显著位，所以你替换表[I] 和表[I-1] 与表[I和1] 和 TABLE [（I-1）及1] 分别为（但只对于主表 - 解决不能当用表格

Second, in the table itself we only really use two rows at any given time: one current row and one previous row. The rows before that (in the main table) are never used again (i.e., to compute row[n] we need the values from row[n-1], but not row[n-2], row[n-3], ... row[0]. To reduce storage, we can make the main table be only two rows, and we swap between the first and second rows. A very C-like trick to do that would be to use only the least significant bit of the row number, so you'd replace table[i] and table[i-1] with table[i&1] and table[(i-1)&1] respectively (but only for the main table -- not when addressing the used table.

这篇关于动态规划总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！