我正在努力理解线性分区问题的动态规划解决方案。我正在读《算法设计手册 http://www.algorist.com/问题在 8.5 节中描述。我已经读过该部分无数次,但我就是不明白。我认为这是一个糟糕的解释(到目前为止我读到的内容要好得多),但我无法很好地理解这个问题,无法寻找替代解释。欢迎链接到更好的解释!
我找到了一个页面,其中的文字与这本书类似(可能来自这本书的第一版):分区问题 http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE45.HTM.
第一个问题:在书中的示例中,分区是按从小到大的顺序排列的。这只是巧合吗?据我所知,元素的顺序对算法并不重要。
这是我对递归的理解:
让我们使用以下序列并将其划分为 4:
{S1...Sn} = 100 150 200 250 300 350 400 450 500
k = 4
第二个问题:这就是我认为递归将如何开始的——我理解正确吗?
第一个递归是:
100 150 200 250 300 350 400 450 | 500 //3 partition to go
100 150 200 250 300 350 400 | 450 | 500 //2 partition to go
100 150 200 250 300 350 | 400 | 450 | 500 //1 partition to go
100 150 200 250 300 | 350 | 400 | 450 | 500 //done
第二次递归是:
100 150 200 250 300 350 400 450 | 500 //3 partition to go
100 150 200 250 300 350 400 | 450 | 500 //2 partition to go
100 150 200 250 300 350 | 400 | 450 | 500 //1 partition to go
100 150 200 250 | 300 350 | 400 | 450 | 500 //done
第三次递归是:
100 150 200 250 300 350 400 450 | 500 //3 partition to go
100 150 200 250 300 350 400 | 450 | 500 //2 partition to go
100 150 200 250 300 350 | 400 | 450 | 500 //1 partition to go
100 150 200 | 250 300 350 | 400 | 450 | 500 //done
第四次递归是:
100 150 200 250 300 350 400 450 | 500 //3 partition to go
100 150 200 250 300 350 400 | 450 | 500 //2 partition to go
100 150 200 250 300 350 | 400 | 450 | 500 //1 partition to go
100 150 | 200 250 300 350 | 400 | 450 | 500 //done
第 5 次递归是:
100 150 200 250 300 350 400 450 | 500 //3 partition to go
100 150 200 250 300 350 400 | 450 | 500 //2 partition to go
100 150 200 250 300 350 | 400 | 450 | 500 //1 partition to go
100 | 150 200 250 300 350 | 400 | 450 | 500 //done
第 6 次递归是:
100 150 200 250 300 350 400 450 | 500 //3 partition to go
100 150 200 250 300 350 400 | 450 | 500 //2 partition to go
100 150 200 250 300 | 350 400 | 450 | 500 //1 partition to go
100 150 200 250 | 300 | 350 400 | 450 | 500 //done
第 7 次递归是:
100 150 200 250 300 350 400 450 | 500 //3 partition to go
100 150 200 250 300 350 400 | 450 | 500 //2 partition to go
100 150 200 250 300 | 350 400 | 450 | 500 //1 partition to go
100 150 200 | 250 300 | 350 400 | 450 | 500 //done
第 8 次递归是:
100 150 200 250 300 350 400 450 | 500 //3 partition to go
100 150 200 250 300 350 400 | 450 | 500 //2 partition to go
100 150 200 250 300 | 350 400 | 450 | 500 //1 partition to go
100 150 | 200 250 300 | 350 400 | 450 | 500 //done
第9次递归是:
100 150 200 250 300 350 400 450 | 500 //3 partition to go
100 150 200 250 300 350 400 | 450 | 500 //2 partition to go
100 150 200 250 300 | 350 400 | 450 | 500 //1 partition to go
100 | 150 200 250 300 | 350 400 | 450 | 500 //done
etc...
这是书中出现的代码:
partition(int s[], int n, int k)
{
int m[MAXN+1][MAXK+1]; /* DP table for values */
int d[MAXN+1][MAXK+1]; /* DP table for dividers */
int p[MAXN+1]; /* prefix sums array */
int cost; /* test split cost */
int i,j,x; /* counters */
p[0] = 0; /* construct prefix sums */
for (i=1; i<=n; i++) p[i]=p[i-1]+s[i];
for (i=1; i<=n; i++) m[i][3] = p[i]; /* initialize boundaries */
for (j=1; j<=k; j++) m[1][j] = s[1];
for (i=2; i<=n; i++) /* evaluate main recurrence */
for (j=2; j<=k; j++) {
m[i][j] = MAXINT;
for (x=1; x<=(i-1); x++) {
cost = max(m[x][j-1], p[i]-p[x]);
if (m[i][j] > cost) {
m[i][j] = cost;
d[i][j] = x;
}
}
}
reconstruct_partition(s,d,n,k); /* print book partition */
}
关于算法的问题:
- 哪些值存储在
m
and d
?
- “成本”是什么意思?它只是分区内元素值的总和吗?还是还有一些额外的更微妙的含义?