y*******8 发帖数: 112 | 1 大家好!我在帖子http://www.mitbbs.com/article_t/JobHunting/32288151.html看到了一个问题,但是楼主没有给出解答,我自己想了半天也不确定,请教哈大家!
有一个长为L的木料需要割开,割的位置在一个数组里A[1...N],从一个地方切开的
cost是当前所切木料的长度,按不同的顺序切割,得到的total cost是不一样的,问怎
么切cost最小。
谢谢大家了! | w***w 发帖数: 84 | 2 Huffman 编码。割一刀看成二叉树的两个分支,总cost就是每个piece乘以其depth,
Huffman 编码正好minimize这一cost. | y*****1 发帖数: 53 | 3 个人见解,错的话大家指教。
如果我理解对的话,在这种cost的情况下,第一刀的cost是定下来了的。那么接下来就
相当于要考虑生下来两半的切割了。大概想象一下,如果切割的靠左了一些,那么左边
的下一刀就会少点,右边的就会多点,反之亦然。如果太左边了右边就多太多,太右边
左边就多太多。所以我们是不是应该找一个比较平均的中点来平衡两边的下一刀。我个
人的考虑是从最靠近中值的点开切。因为比如选的是中值靠左的那一个切点,那么就要
在右边更长的长度上多切一刀,左边更短的长度上少切一刀,感觉是划不来的。不知道
这样对不对。。。 | n*******e 发帖数: 37 | 4 好像看过类似的题目, 但不是很确定了, 说说我的想法, 大家一起讨论吧.
观察这个简单例子, L = 8, A[] = {1,2,3,4,5,6,7}, 也就是要把木板切成8等份
尝试使用以下两种不同切法:
1. 天真的切法, 按照A[]的顺序: 1,2,3,4,5,6,7来切, cost会是8+7+6+5+4+3+2=35
2. 聪明的切法, 把木板尽量切成1/2长度, 剩下的两半再各切成1/4长度, 剩下的4个1/
4木板再各切成1/8长度, 也就是照此顺序: 4,2,1,3,6,5,7 (或是4,2,6,1,3,5,7也对),
cost会是8+4+2+2+4 +2+2=24
我想第二种切法是最佳解了(忘了如何做严谨的证明), 这个解法应该可以算是greedy +
divide & conquer, 每次尽量把当前处理的那块木板砍成其长度的一半,并按照此规则
继续处理砍出来的小块木板, 直到处理完所有切割位置.
实现时, 用dfs实现divide & conquer, 类似merge sort的做法. 每个function call用
O(n)找出能把当前木板砍成最接近一半的切割点, 再用两个subcalls下去处理被砍出来
的两小块木板.
time complexity是O(nlogn) | n*******e 发帖数: 37 | 5 证明就是像wocow说的那样, 但要记得还真不容易啊 | n******a 发帖数: 83 | 6 请教一下,huffman编码怎么保证每次取的是相邻的。
我只知道这个题目可以用DP做。
【在 w***w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Huffman 编码。割一刀看成二叉树的两个分支,总cost就是每个piece乘以其depth, : Huffman 编码正好minimize这一cost.
| w***w 发帖数: 84 | 7 嗯,我读题不仔细,Huffman 编码允许不同的order,只要最后切出来的长度符合要求就
行,或许这是interview的第二问。对 fixed order 或许只能 DP. | y*******8 发帖数: 112 | | y*******8 发帖数: 112 | 9 你好!
我不太明白为什么是:“实现时, 用dfs实现divide & conquer”?我的想法是用递归
做的DFS,您的意思是这样吗?
每个function call用O(n)找出能把当前木板砍成最接近一半的切割点:
可以先排序在二分查找,应该是O(logN)吧?
谢谢了!
1/
),
+
【在 n*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好像看过类似的题目, 但不是很确定了, 说说我的想法, 大家一起讨论吧. : 观察这个简单例子, L = 8, A[] = {1,2,3,4,5,6,7}, 也就是要把木板切成8等份 : 尝试使用以下两种不同切法: : 1. 天真的切法, 按照A[]的顺序: 1,2,3,4,5,6,7来切, cost会是8+7+6+5+4+3+2=35 : 2. 聪明的切法, 把木板尽量切成1/2长度, 剩下的两半再各切成1/4长度, 剩下的4个1/ : 4木板再各切成1/8长度, 也就是照此顺序: 4,2,1,3,6,5,7 (或是4,2,6,1,3,5,7也对), : cost会是8+4+2+2+4 +2+2=24 : 我想第二种切法是最佳解了(忘了如何做严谨的证明), 这个解法应该可以算是greedy + : divide & conquer, 每次尽量把当前处理的那块木板砍成其长度的一半,并按照此规则 : 继续处理砍出来的小块木板, 直到处理完所有切割位置.
| y*******8 发帖数: 112 | 10 实在抱歉!我知道Huffman coding,但是我还是不太明白怎么应用Huffman coding到这
个问题。请问您能不能举个简单的例子?比例长度为8,锯的点是[1,4,5]。
另外,我的想法和neotheone差不多,每次都尽量寻找中间的点去锯。请问“对 fixed
order 或许只能 DP”这句话怎么理解。
多谢了!
【在 w***w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 嗯,我读题不仔细,Huffman 编码允许不同的order,只要最后切出来的长度符合要求就 : 行,或许这是interview的第二问。对 fixed order 或许只能 DP.
| | | w***w 发帖数: 84 | 11 DP 其实就是递归。 设c(i,j)是从i-th cut 到j-th cut的线段的最小cost, 就有递归
式,c(i,j) = min_{i
不能直接递归去解,否则会指数爆炸。DP 的trick就是递归过程中记住所有见过的解,
每次递归先去查解是否已存在。或者是通常看到的递推的自底而上的填表式的解法。
至于Huffman编码,假设题目是切出要求长度的一些木块但并不限定order的话,这样你
可以把长度看成是概率 (设木板总长是1),那么这里的cost定义就等价于平均码字长
度, 因为每一小段contribute的cost就是把它切出来需要的cut数。 | f*********0 发帖数: 17 | 12 我也觉得应该从中间切,可是怎么证明呢?现在就能证明切割少于5的情况。
另外可以O(logn)找最接近中点的位置啊,就是在一个排好序的数组中,找最接近某个
值的数嘛。
PS:这题和huffman编码没关系吧,因为cost并不是码字长度啊,因为每一小段
contribute的cost不是它被切出来需要的cut数啊 | n*******e 发帖数: 37 | 13 对喔应该用binary search可以O(logn)找到要切的点, 谢谢提醒
【在 f*********0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我也觉得应该从中间切,可是怎么证明呢?现在就能证明切割少于5的情况。 : 另外可以O(logn)找最接近中点的位置啊,就是在一个排好序的数组中,找最接近某个 : 值的数嘛。 : PS:这题和huffman编码没关系吧,因为cost并不是码字长度啊,因为每一小段 : contribute的cost不是它被切出来需要的cut数啊
| n*******e 发帖数: 37 | 14 是的 应该用binary search才对
说是divide & conquer只是因为觉得很像quick sort, merge sort的做法
其实就是DFS
【在 y*******8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你好! : 我不太明白为什么是:“实现时, 用dfs实现divide & conquer”?我的想法是用递归 : 做的DFS,您的意思是这样吗? : 每个function call用O(n)找出能把当前木板砍成最接近一半的切割点: : 可以先排序在二分查找,应该是O(logN)吧? : 谢谢了! : : 1/ : ), : +
| l*********8 发帖数: 4642 | 15 从中间切不一定对。
反例:
总长12, 切割位置[5, 6, 7]
如果从中间切, 则第一刀在位置6, 第二三刀位置在5和7. 总共cost: 12 + 6 + 6 =
24
更好的解法是:
第一刀在位置5, 第二刀位置7, 第三刀位置6, 总共cost:12 + 7 + 2 = 21
此题正解还是DP。
【在 f*********0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我也觉得应该从中间切,可是怎么证明呢?现在就能证明切割少于5的情况。 : 另外可以O(logn)找最接近中点的位置啊,就是在一个排好序的数组中,找最接近某个 : 值的数嘛。 : PS:这题和huffman编码没关系吧,因为cost并不是码字长度啊,因为每一小段 : contribute的cost不是它被切出来需要的cut数啊
| w***w 发帖数: 84 | | f*********0 发帖数: 17 | 17 赞!
=
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 从中间切不一定对。 : 反例: : 总长12, 切割位置[5, 6, 7] : 如果从中间切, 则第一刀在位置6, 第二三刀位置在5和7. 总共cost: 12 + 6 + 6 = : 24 : 更好的解法是: : 第一刀在位置5, 第二刀位置7, 第三刀位置6, 总共cost:12 + 7 + 2 = 21 : 此题正解还是DP。
| l***i 发帖数: 1309 | | f**x 发帖数: 21 | 19 我写的实现 只简单测了一个例子,欢迎review
int dp[256][256];
int min_cuts(int *cuts, int start, int end) {
if (dp[start][end] >= 0) return dp[start][end];
if (end - start == 1) {
return dp[start][end] = 0;
} else if (end - start == 2) {
return dp[start][end] = cuts[end] - cuts[start];
} else {
int this_cut = cuts[end] - cuts[start];
dp[start][end] = INT32_MAX;
for(int i = start + 2; i < end; i++) {
dp[start][end] = min(dp[start][end],
min_cuts(cuts, start, i) + min_cuts(cuts, i, end));
}
return dp[start][end] += this_cut;
}
}
int main() {
int cuts[] = {0, 1, 4, 5, 15, 18};
memset(dp, -1, sizeof(dp));
printf("%d\n", min_cuts(cuts, 0, 5));
} | T*****u 发帖数: 7103 | | n*******e 发帖数: 37 | 21 讚 这还真是想不到啊...
=
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 从中间切不一定对。 : 反例: : 总长12, 切割位置[5, 6, 7] : 如果从中间切, 则第一刀在位置6, 第二三刀位置在5和7. 总共cost: 12 + 6 + 6 = : 24 : 更好的解法是: : 第一刀在位置5, 第二刀位置7, 第三刀位置6, 总共cost:12 + 7 + 2 = 21 : 此题正解还是DP。
|
|