动态规划和 [英] 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?

我有点想不通.

推荐答案

通常的措辞是您正在寻找最接近但不超过 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.

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

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

我们通常还希望跟踪实际用于产生结果的项目.为此，我们将表中给定点的布尔值设置为 true，当且仅当我们使用该行的新输入计算表中该点的值(而不是仅仅复制前一行的最佳值).最好的结果是在右下角，所以我们从那里开始，然后一次在桌子上向后走一排.当我们到达该列的布尔值设置为 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] << "
";
    std::cout << "Used items where:
";
    int column = MAX;
    for (int i=rows; i>-1; i--)
        if (used[i][column]) {
            std::cout << "	v[" << i << "] = " << v[i] << "
";
            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).

其次，在表格本身中，我们在任何给定时间实际上只使用两行:当前行和前一行.之前的行(在主表中)不再使用(即，为了计算 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 表时.

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屋！