1

我试图解决以下问题：

加权和问题

我之前做过的最接近的问题是 Kadane 的算法，所以我尝试了“此处最大结尾”的方法，这导致了以下基于 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[ii][j] 是问题的答案，与我们的问题相同，将 n 替换为 i，将 m 替换为j. 也就是我们建立一个f[i][j]的表，我们最终的答案是f[n-1][m]（也就是我们使用memoization）。现在注意到计算条目 f[i][j] 只需要前一列，只保留数组就足够了。这些数组是“a”和“b”。

抱歉，篇幅太长，忍不住了。:(

4

2 回答 2

0

Try 0/1 Knapsack without repetition approach where at each step we decide whether to include an item or not.

Let MWS(i, j) represent the optimal maximum weighted sum of the sub-problem C[i...N] where i varies from 0 <= i <= N and 1 <= j <= M, and our goal is to find out the value of MWS(0, 1).

MWS(i, j) can be represented in the recursive ways as follow.

enter image description here

I am leaving the boundary conditions handling as an exercise for you.

于 2012-06-02T17:43:17.290 回答
0

Your general approach is correct. But there is a problem with your algorithm.

You could replace the body of the inner loop

    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;

with 

   b[x] = MAX(b[x-1],a[x-1] + y * C[x]);

This will improve the time complexity of the algorithm. I.e. avoid recomputing b[i] for all i < x. A common trait in dynamic programming.

于 2012-06-02T17:09:20.217 回答