algorithm - 具有约束的数组中的最大和

Question

我有这个问题，给定一个正数数组，我必须找到元素的最大总和，这样就不会选择两个相邻的元素。最大值必须小于某个给定的 K。我尝试在没有 k 的情况下思考类似的问题，但到目前为止我都失败了。对于后一个问题，我有以下 dp-ish soln

    int sum1,sum2 = 0;
    int sum = sum1 = a[0];

    for(int i=1; i<n; i++)
    {
        sum = max(sum2 + a[i], sum1);
        sum2 = sum1;
        sum1 = sum;
    }

有人可以告诉我如何处理我目前的问题吗？

Answer 1

我能想到的最好的是 O(n*K) dp:

int sums[n][K+1] = {{0}};
int i, j;
for(j = a[0]; j <= K; ++j) {
    sums[0][j] = a[0];
}
if (a[1] > a[0]) {
    for(j = a[0]; j < a[1]; ++j) {
        sums[1][j] = a[0];
    }
    for(j = a[1]; j <= K; ++j) {
        sums[1][j] = a[1];
    }
} else {
    for(j = a[1]; j < a[0]; ++j) {
        sums[1][j] = a[1];
    }
    for(j = a[0]; j <= K; ++j) {
        sums[1][j] = a[0];
    }
}
for(i = 2; i < n; ++i) {
    for(j = 0; j <= K && j < a[i]; ++j) {
        sums[i][j] = max(sums[i-1][j],sums[i-2][j]);
    }
    for(j = a[i]; j <= K; ++j) {
        sums[i][j] = max(sums[i-1][j],a[i] + sums[i-2][j-a[i]]);
    }
}

sums[i][j] 包含a[0..i] 的非相邻元素的最大和不超过j。最后的解决方案是 sums[n-1][K]。