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 的大作中提到】
: 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 的大作中提到】
: 好像看过类似的题目, 但不是很确定了, 说说我的想法, 大家一起讨论吧.
: 观察这个简单例子, 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 的大作中提到】
: 嗯,我读题不仔细，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 的大作中提到】
: 我也觉得应该从中间切，可是怎么证明呢？现在就能证明切割少于5的情况。
: 另外可以O(logn)找最接近中点的位置啊，就是在一个排好序的数组中，找最接近某个
: 值的数嘛。
: PS：这题和huffman编码没关系吧，因为cost并不是码字长度啊，因为每一小段
: contribute的cost不是它被切出来需要的cut数啊
| n*******e
发帖数: 37 | 14 是的 应该用binary search才对
说是divide & conquer只是因为觉得很像quick sort, merge sort的做法
其实就是DFS
【在 y*******8 的大作中提到】
: 你好！
: 我不太明白为什么是：“实现时, 用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 的大作中提到】
: 我也觉得应该从中间切，可是怎么证明呢？现在就能证明切割少于5的情况。
: 另外可以O(logn)找最接近中点的位置啊，就是在一个排好序的数组中，找最接近某个
: 值的数嘛。
: PS：这题和huffman编码没关系吧，因为cost并不是码字长度啊，因为每一小段
: contribute的cost不是它被切出来需要的cut数啊
| w***w
发帖数: 84 | | f*********0
发帖数: 17 | 17 赞！
=
【在 l*********8 的大作中提到】
: 从中间切不一定对。
: 反例：
: 总长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 的大作中提到】
: 从中间切不一定对。
: 反例：
: 总长12, 切割位置[5, 6, 7]
: 如果从中间切， 则第一刀在位置6， 第二三刀位置在5和7. 总共cost: 12 + 6 + 6 =
: 24
: 更好的解法是：
: 第一刀在位置5， 第二刀位置7， 第三刀位置6， 总共cost：12 + 7 + 2 = 21
: 此题正解还是DP。
|
|
