c - 找到所有 m 子序列的最大加权和

Question

我正在尝试解决以下问题:

Weighted Sum Problem

我之前做的最接近的问题是Kadane的算法，所以我尝试了“max ending here”的方法，导致了下面的基于DP的程序。这个想法是将问题分解成更小的相同问题(通常的 DP)。

#include<stdio.h>
#include<stdlib.h>


main(){
int i, n, m, C[20002], max, y, x, best, l, j;
int a[20002], b[20002];
scanf("%d %d", &n, &m);
for(i=0;i<n;i++){
    scanf("%d",&C[i]);
}
a[0] = C[0];
max = C[0];
for(i=1;i<n;i++){
    max = (C[i]>max) ? C[i] : max;
    a[i] = max;
}

for(l=0;l<n;l++){
    b[l] = 0;
}

for(y=2;y<m+1;y++){

    for(x=y-1;x<n;x++){

        best = max = 0;
        for(j=0;j<y;j++){
        max += (j+1) * C[j];
        }

        for(i=y-1;i<x+1;i++){
            best = a[i-1] + y * C[i];
            max = (best>max) ? best : max;
        }
        b[x] = max;
    }

    for(l=0;l<n;l++){
    a[l] = b[l];                 
    }
}
printf("%d\n",b[n-1]);
system("PAUSE");
return 0;
}

但是这个程序在指定的时间限制内不起作用(空间限制可以)。请给我一个关于这个问题所用算法的提示。

编辑。

代码解释如下:和 Kadane 一样，我的想法是查看特定的 C[i]，然后对以 C[i] 结尾的 m 子序列取最大加权和，最后取所有 i 上所有此类值的最大值。这会给我们答案。现在请注意，当您查看以 C[i] 结尾的 m 子序列并取最大加权和时，这相当于取 C[0] 中包含的 (m-1)-子序列的最大加权和到 C[i-1]。这是一个较小的问题，与我们原来的问题相同。所以我们使用递归。为了避免对函数的双重调用，我们制作了一个值表 f[i][j]，其中 f[i-i][j] 是问题的答案，它与我们的问题相同，其中 n 替换为 i，m 替换为j.也就是我们建一个f[i][j]的表，我们最终的答案是f[n-1][m](也就是我们用memoization)。现在注意到只需要前一列来计算条目 f[i][j]，只保留数组就足够了。这些数组是“a”和“b”。

抱歉篇幅较长，没办法。 :(

Answer 1

尝试 0/1 Knapsack without repetition在每一步我们决定是否包含一个项目的方法。

让MWS(i, j)代表 optimal maximum weighted sum子问题的 C[i...N]其中 i不同于 0 <= i <= N和 1 <= j <= M , 我们的目标是找出 MWS(0, 1) 的值.

MWS(i, j) 可以递归表示如下。

我将边界条件处理作为练习留给您。