algorithm - 指数总和为常量的最大总和

Question

我正在为以下问题寻找一种有效的算法:

有一个包含值的数组，即(注意索引 0 是故意省略的)

Index  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12
Value 17, 12,  5, 22,  3, 12,  6, 13,  7,  0,  2, 15

我需要找到的是这些约束下的索引子集:

1. 索引的数量是恒定的(即 3)
2. 索引的总和是常数(即 20)
3. 每个索引只能出现一次(因此 [2, 9, 9] 不是有效的解决方案)
4. 值的总和是最大值。

例如，如果子集长度为 3，总和为 20，则所有可能的解决方案都是

Indices: [1, 7, 12] Sum of values: 17 + 6 + 15 =  38
Indices: [1, 8, 11] Sum of values: 17 + 13 + 2 =  32
Indices: [1, 9, 10] Sum of values: 17 + 7 + 0 =   24
Indices: [2, 6, 12] Sum of values: 12 + 12 + 15 = 39
Indices: [2, 7, 11] Sum of values: 12 + 6 + 2 =   20
Indices: [2, 8, 10] Sum of values: 12 + 13 + 0 =  25
Indices: [3, 5, 12] Sum of values: 5 + 3 + 15 =   23
Indices: [3, 6, 11] Sum of values: 5 + 12 + 2 =   19
Indices: [3, 7, 10] Sum of values: 5 + 6 + 0 =    11
Indices: [3, 8, 9]  Sum of values: 5 + 13 + 7 =   25
Indices: [4, 5, 11] Sum of values: 22 + 3 + 2 =   27
Indices: [4, 6, 10] Sum of values: 22 + 12 + 0 =  34
Indices: [4, 7, 9]  Sum of values: 22 + 6 + 7 =   35
Indices: [5, 6, 9]  Sum of values: 3 + 12 + 7 =   22
Indices: [5, 7, 8]  Sum of values: 3 + 6 + 13 =   22

其中 [2, 6, 12] 是最优解，因为它的值和最大。

目前我使用稍微修改过的分区算法遍历所有可能的组合，该算法随着索引总和的增长呈指数增长，所以我想知道是否有更好的方法？

Answer 1

解O(I.S.K)

让我们先做一些命名:

• I 是最大的索引(在您的示例中为 12)
• S 是选择索引的值的总和(在您的示例中为 20)
• K是选择的索引个数
• V[] 链接到索引的值数组
• maxsum(s, i, k) 使用k 索引可达到的最大总和，所有不同，其值小于或等于i，其总和为s。

然后你想求maxsum(S, I, K)

您的问题展示了一些良好的特性:

• 最优子结构
• 冗余子问题

例如，当尝试计算 maxsum(s, i, k) 时，我可以不使用索引 i，在这种情况下，值为 maxsum (s, i-1, k)。或者我可以使用索引 i。在这种情况下，我想解决子问题:索引小于或等于 i-1 且其和为 s-i 的最大和是多少 s-i 使用 k-1 这样的索引。这是值:V[i] + maxsum(s-i, i-1, k-1)。

因为我们想要达到最大总和，我们最终得到:(编辑:将 maxsum(s-i, i-1, k) 更正为 maxsum(s-i, i-1, k -1))

maxsum(s, i, k) = max{ maxsum(s, i-1, k) ; V[i] + maxsum(s-i, i-1, k-1) }

这是 dynamic programming 可以解决的典型问题.

这是一个 C++ 程序示例，它解决了 O(I.S.K)(空间和时间)中的问题。

我们可以以更大的时间复杂度为代价将空间复杂度提高到 O(I.S):O(I.S.K²)。

如何使用程序

g++ -std=c++14 -g -Wall -O0    dp.cpp   -o dp
./dp input.txt

其中 input.txt 是具有以下格式的文件:

1. 第一行包含三个整数:I S K
2. 第二行包含 I 个整数，索引的值

示例运行

---- K=1 ----
      17  12   5  22   3  12   6  13   7   0   2  15 
     [ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11][12]
[ 1]  17  17  17  17  17  17  17  17  17  17  17  17 
[ 2]      12  12  12  12  12  12  12  12  12  12  12 
[ 3]           5   5   5   5   5   5   5   5   5   5 
[ 4]              22  22  22  22  22  22  22  22  22 
[ 5]                   3   3   3   3   3   3   3   3 
[ 6]                      12  12  12  12  12  12  12 
[ 7]                           6   6   6   6   6   6 
[ 8]                              13  13  13  13  13 
[ 9]                                   7   7   7   7 
[10]                                       0   0   0 
[11]                                           2   2 
[12]                                              15 
[13]                                                 
[14]                                                 
[15]                                                 
[16]                                                 
[17]                                                 
[18]                                                 
[19]                                                 
[20]                                                 
---- K=2 ----
      17  12   5  22   3  12   6  13   7   0   2  15 
     [ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11][12]
[ 1]                                                 
[ 2]      12  12  12  12  12  12  12  12  12  12  12 
[ 3]      29  29  29  29  29  29  29  29  29  29  29 
[ 4]          22  22  22  22  22  22  22  22  22  22 
[ 5]          17  39  39  39  39  39  39  39  39  39 
[ 6]              34  34  34  34  34  34  34  34  34 
[ 7]              27  27  29  29  29  29  29  29  29 
[ 8]                   8  24  24  24  24  24  24  24 
[ 9]                  25  25  25  30  30  30  30  30 
[10]                      34  34  34  34  34  34  34 
[11]                      15  28  28  28  28  28  28 
[12]                           9  35  35  35  35  35 
[13]                          18  18  29  29  29  32 
[14]                              25  25  25  25  27 
[15]                              19  19  19  24  24 
[16]                                  13  13  13  37 
[17]                                  20  20  20  20 
[18]                                      13  13  27 
[19]                                       7  15  21 
[20]                                           9  28 
---- K=3 ----
      17  12   5  22   3  12   6  13   7   0   2  15 
     [ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11][12]
[ 1]                                                 
[ 2]                                                 
[ 3]                                                 
[ 4]                                                 
[ 5]          17  17  17  17  17  17  17  17  17  17 
[ 6]          34  34  34  34  34  34  34  34  34  34 
[ 7]              51  51  51  51  51  51  51  51  51 
[ 8]              44  44  44  44  44  44  44  44  44 
[ 9]              39  39  41  41  41  41  41  41  41 
[10]                  42  42  42  42  42  42  42  42 
[11]                  37  51  51  51  51  51  51  51 
[12]                  30  46  46  46  46  46  46  46 
[13]                      39  40  52  52  52  52  52 
[14]                      20  35  47  47  47  47  47 
[15]                      37  37  42  42  42  42  44 
[16]                          31  37  37  37  41  41 
[17]                          40  40  40  40  40  54 
[18]                          21  47  47  47  47  49 
[19]                              41  41  41  41  44 
[20]                              22  35  35  35  39 
index:  12 sum:  20
index:   6 sum:   8
index:   2 sum:   2
max sum: 39

源代码

#include <cstdio>
#include <iomanip>
#include <iostream>
#include <limits>
#include <valarray>
#include <vector>

using namespace std;

auto const INF = numeric_limits<double>::infinity();

struct matrix {
    matrix(size_t rows, size_t cols, double value)
        : cells(value, rows*cols)
        , rows(rows)
        , cols(cols)
        , value(value)
    {}

    double& operator() (int r, int c)
    {
        if(r < 0 || c < 0)
            return value;

        return cells[r*cols+c];
    }

    valarray<double> cells;
    size_t rows;
    size_t cols;
    double value;
};

int main(int argc, char* argv[]) {
    if(argc > 1)
        freopen(argv[1], "r", stdin);

    // I: max index
    // S: sum of indices
    // K: number of indices in the sum S
    int I, S, K;
    cin >> I >> S >> K;

    // load values
    vector<double> V(I+1, 0);
    for(int i=1; i<=I; ++i)
        cin >> V[i];

    // dynamic programming:
    // --------------------
    // maxsum(i, s, k) is the maximal sum reachable using 'k' indices, less
    // than or equal to 'i', all differents, and having a sum of 's'
    //
    // maxsum(i, s, k) =
    //   -oo if i > s
    //
    //   -oo if i < s && k == 1
    //
    //   V[s] if i >= s && s <= I && k == 1
    //   -oo  if (i < s || s > I) && k == 1
    //   
    //   max { V[i] + maxsum(i-1, S-i, k-1), maxsum(i-1, S, k) }
    vector<matrix> maxsum(K+1, matrix(S+1, I+1, -INF));

    // initialize K=1
    for(int s=0; s<=I && s<=S; ++s) {
        for(int i=s; i<=I; ++i) {
            maxsum[1](s, i) = V[s];
        }
    }

    // K > 1
    for(int k=2; k<=K; ++k) {
        for(int s=2; s<=S; ++s) {
            for(int i=1; i<=I; ++i) {
                auto l = V[i] + maxsum[k-1](s-i, i-1);
                auto r = maxsum[k](s, i-1);
                maxsum[k](s, i) = max(l, r);
            }
        }
    }

    // display the whole dynamic programming tables (optional)
    for(int k=1; k<=K; ++k) {
        cout << "---- K=" << k << " ----\n";
        cout << "     ";
        for(int i=1; i<=I; ++i) {
            cout << setw(3) << V[i] << ' ';
        }
        cout << '\n';
        cout << "     ";
        for(int i=1; i<=I; ++i) {
            cout << '[' << setw(2) << i << ']';
        }
        cout << '\n';
        for(int s=1; s<=S; ++s) {
            cout << '[' << setw(2) << s << "] ";
            for(int i=1; i<=I; ++i) {
                if(maxsum[k](s, i) == -INF) {
                    cout << "    ";
                } else {
                    cout << setw(3) << maxsum[k](s, i) << ' ';
                }
            }
            cout << '\n';
        }
    }

    // output the indices belonging to the solution by working backward in the
    // dynamic programming tables
    int t_S = S;
    int t_I = I;
    for(int k=K; k>=1; --k) {
        if(t_I <= 0 || t_S <= 0) {
            cout << "error...\n";
            break;
        }
        auto m = maxsum[k](t_S, t_I);
        int i;
        for(i=t_I; i>=1; --i) {
            if(maxsum[k](t_S, i) != m)
                break;
        }
        cout << "index: " << setw(3) << (i+1) << ' ';
        cout << "sum: " << setw(3) << t_S << '\n';
        t_I = i;
        t_S = t_S - i - 1;
    }

    cout << "max sum: " << maxsum[K](S, I) << '\n';
}