通常的用语是您正在寻找最接近但不超过K的值。如果您的意思是“小于K”，则仅表示您的K值比平时大一个。如果您真正的意思是“不等于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-
在寻址表时不可用。table[i-1]``table[i&1]``table[(i-1)&1]``used