请教一道rocket fuel DP题 - 未名空间MITBBS历史存档

f*m2013-06-23 07:06

1 楼

如何做？
大牛贴过了这题，我怕被大家的讨论淹没了，单独把他列出来。这题好像是
Introduction to algorithm的一道课后题。
(2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
，求这张纸所能剪出的最大值。

x*w2013-06-23 07:06

2 楼

CLRS有个类似的，rod cutting，不过这个是二维的

【在 f*********m 的大作中提到】

: 如何做？
: 大牛贴过了这题，我怕被大家的讨论淹没了，单独把他列出来。这题好像是
: Introduction to algorithm的一道课后题。
: (2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
: ，求这张纸所能剪出的最大值。

r*h2013-06-23 07:06

3 楼

二维的话可能会有面积不刚好的情况吧（比如说矩形缺了一个左下角）
这个时候要如何状态压缩呢

【在 x*********w 的大作中提到】

:
: CLRS有个类似的，rod cutting，不过这个是二维的

f*m2013-06-23 07:06

4 楼

对，这就是难点所在。

【在 r**h 的大作中提到】

: 二维的话可能会有面积不刚好的情况吧（比如说矩形缺了一个左下角）
: 这个时候要如何状态压缩呢

x*w2013-06-23 07:06

5 楼

想了一个实现起来超复杂的。
建立一个4维dp matrix. dp[i][j][k][l]为坐标矩阵(i,j), (k,l)的最优解
for (l = 1; l <= max_l; l++) //长度递增
{
for (w = 1; w <= max_w; w++) //宽度递增
{
对每一个sub matrix (max_w*max_w*max_l*max_l 个)
{
如果在一个大矩阵中挖去了一个小矩阵，会把剩下的空间分成8块小的
matrix
取所有可能组合的max value，考虑横跨各种两个小矩阵的情况
}
}
}

w*m2013-06-23 07:06

6 楼

靠，这是我面试别人的一道题的2D version。
我的题是，有一句话，和一个词典（记录着每个词的权重，假设每个可能的词都有），
如何把这句话分成词，让最后之和最大。没一个人能答出来。因为我面的都是烙印

【在 f*********m 的大作中提到】

: 如何做？
: 大牛贴过了这题，我怕被大家的讨论淹没了，单独把他列出来。这题好像是
: Introduction to algorithm的一道课后题。
: (2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
: ，求这张纸所能剪出的最大值。

s*s2013-06-23 07:06

7 楼

就是那个cut rope的二维扩展。用DP来做。
int getPrice(int L, int W, vector > pieces) {
int vector > M(L+1, vector(W+1, 0));
/*
Use DP.
For , cut the pieces from the left top corner we c
an get three sub-problems:
(1). getPrice(L-l(k), W, prices) & getPrice(l(k), W-w(k), prices)
(2). getPrice(L, W-w(k), prices) & getPrice(L-l(k), w(k), prices)
*/
for(int i=0; i<=L; ++i) {
for(int j=0; jM[i][j] = 0;
for(int k=0; kif(i>=pieces[k].length && j>=pieces[k].width) {
M[i][j] = max(M[i][j], prices[k].price + M[i-pieces[k].l
ength][j] + M[pieces[k].length][j-pieces[k].width]);
M[i][j] = max(M[i][j], prices[k].price + M[i][j-pieces[k
].width] + M[i-pieces[k].length][pieces[k].width]);
}
}
}
return M[L][W];
}

【在 f*********m 的大作中提到】

: 如何做？
: 大牛贴过了这题，我怕被大家的讨论淹没了，单独把他列出来。这题好像是
: Introduction to algorithm的一道课后题。
: (2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
: ，求这张纸所能剪出的最大值。

f*m2013-06-23 07:06

8 楼

这个算法好，不过有可能一个piece被用了多次吧？

c

【在 s*******s 的大作中提到】

: 就是那个cut rope的二维扩展。用DP来做。
: int getPrice(int L, int W, vector > pieces) {
: int vector > M(L+1, vector(W+1, 0));
: /*
: Use DP.
: For , cut the pieces from the left top corner we c
: an get three sub-problems:
: (1). getPrice(L-l(k), W, prices) & getPrice(l(k), W-w(k), prices)
: (2). getPrice(L, W-w(k), prices) & getPrice(L-l(k), w(k), prices)
: */

s*t2013-06-23 07:06

9 楼

注释部分的想法貌似是对的，可以递归，后面的实现好像有问题
假设L=100，W=100，求M[1][1]的时候要用到M[99][100]、M[100][99]、M[99][99]，而
后面这三个值还没有初始化，是我理解错了还是这个实现有问题？

c

【在 s*******s 的大作中提到】

: 就是那个cut rope的二维扩展。用DP来做。
: int getPrice(int L, int W, vector > pieces) {
: int vector > M(L+1, vector(W+1, 0));
: /*
: Use DP.
: For , cut the pieces from the left top corner we c
: an get three sub-problems:
: (1). getPrice(L-l(k), W, prices) & getPrice(l(k), W-w(k), prices)
: (2). getPrice(L, W-w(k), prices) & getPrice(L-l(k), w(k), prices)
: */

f*m2013-06-23 07:06

10 楼

如何做？
大牛贴过了这题，我怕被大家的讨论淹没了，单独把他列出来。这题好像是
Introduction to algorithm的一道课后题。
(2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
，求这张纸所能剪出的最大值。

x*w2013-06-23 07:06

11 楼

CLRS有个类似的，rod cutting，不过这个是二维的

【在 f*********m 的大作中提到】

: 如何做？
: 大牛贴过了这题，我怕被大家的讨论淹没了，单独把他列出来。这题好像是
: Introduction to algorithm的一道课后题。
: (2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
: ，求这张纸所能剪出的最大值。

r*h2013-06-23 07:06

12 楼

二维的话可能会有面积不刚好的情况吧（比如说矩形缺了一个左下角）
这个时候要如何状态压缩呢

【在 x*********w 的大作中提到】

:
: CLRS有个类似的，rod cutting，不过这个是二维的

f*m2013-06-23 07:06

13 楼

对，这就是难点所在。

【在 r**h 的大作中提到】

: 二维的话可能会有面积不刚好的情况吧（比如说矩形缺了一个左下角）
: 这个时候要如何状态压缩呢

x*w2013-06-23 07:06

14 楼

想了一个实现起来超复杂的。
建立一个4维dp matrix. dp[i][j][k][l]为坐标矩阵(i,j), (k,l)的最优解
for (l = 1; l <= max_l; l++) //长度递增
{
for (w = 1; w <= max_w; w++) //宽度递增
{
对每一个sub matrix (max_w*max_w*max_l*max_l 个)
{
如果在一个大矩阵中挖去了一个小矩阵，会把剩下的空间分成8块小的
matrix
取所有可能组合的max value，考虑横跨各种两个小矩阵的情况
}
}
}

w*m2013-06-23 07:06

15 楼

靠，这是我面试别人的一道题的2D version。
我的题是，有一句话，和一个词典（记录着每个词的权重，假设每个可能的词都有），
如何把这句话分成词，让最后之和最大。没一个人能答出来。因为我面的都是烙印

【在 f*********m 的大作中提到】

: 如何做？
: 大牛贴过了这题，我怕被大家的讨论淹没了，单独把他列出来。这题好像是
: Introduction to algorithm的一道课后题。
: (2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
: ，求这张纸所能剪出的最大值。

s*s2013-06-23 07:06

16 楼

就是那个cut rope的二维扩展。用DP来做。
int getPrice(int L, int W, vector > pieces) {
int vector > M(L+1, vector(W+1, 0));
/*
Use DP.
For , cut the pieces from the left top corner we c
an get three sub-problems:
(1). getPrice(L-l(k), W, prices) & getPrice(l(k), W-w(k), prices)
(2). getPrice(L, W-w(k), prices) & getPrice(L-l(k), w(k), prices)
*/
for(int i=0; i<=L; ++i) {
for(int j=0; jM[i][j] = 0;
for(int k=0; kif(i>=pieces[k].length && j>=pieces[k].width) {
M[i][j] = max(M[i][j], prices[k].price + M[i-pieces[k].l
ength][j] + M[pieces[k].length][j-pieces[k].width]);
M[i][j] = max(M[i][j], prices[k].price + M[i][j-pieces[k
].width] + M[i-pieces[k].length][pieces[k].width]);
}
}
}
return M[L][W];
}

【在 f*********m 的大作中提到】

: 如何做？
: 大牛贴过了这题，我怕被大家的讨论淹没了，单独把他列出来。这题好像是
: Introduction to algorithm的一道课后题。
: (2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
: ，求这张纸所能剪出的最大值。

f*m2013-06-23 07:06

17 楼

这个算法好，不过有可能一个piece被用了多次吧？

c

【在 s*******s 的大作中提到】

: 就是那个cut rope的二维扩展。用DP来做。
: int getPrice(int L, int W, vector > pieces) {
: int vector > M(L+1, vector(W+1, 0));
: /*
: Use DP.
: For , cut the pieces from the left top corner we c
: an get three sub-problems:
: (1). getPrice(L-l(k), W, prices) & getPrice(l(k), W-w(k), prices)
: (2). getPrice(L, W-w(k), prices) & getPrice(L-l(k), w(k), prices)
: */

s*t2013-06-23 07:06

18 楼

注释部分的想法貌似是对的，可以递归，后面的实现好像有问题
假设L=100，W=100，求M[1][1]的时候要用到M[99][100]、M[100][99]、M[99][99]，而
后面这三个值还没有初始化，是我理解错了还是这个实现有问题？

c

【在 s*******s 的大作中提到】

: 就是那个cut rope的二维扩展。用DP来做。
: int getPrice(int L, int W, vector > pieces) {
: int vector > M(L+1, vector(W+1, 0));
: /*
: Use DP.
: For , cut the pieces from the left top corner we c
: an get three sub-problems:
: (1). getPrice(L-l(k), W, prices) & getPrice(l(k), W-w(k), prices)
: (2). getPrice(L, W-w(k), prices) & getPrice(L-l(k), w(k), prices)
: */

k*o2013-06-23 07:06

19 楼

mark