d****n
发帖数: 233 | 1 This question can be asked in various forms, here is the one I was asked:
A carpenter is trying to build some furniture, he need a list wood blocks
with different length, say L1, L2, ... Ln where 1 <= Li <= LMAX for i = 1,2.
. n. He need to purchase whole wood blocks from the shop. The wood blocks
in the shop are fixed length, say LEN, LEN >= LMAX.
Can you help the carpenter save money by figuring out the minimum number of
whole wood blocks he need to purchase?
Any idea on how to solve this? | B*****t
发帖数: 335 | 2 这些都是背包问题变体
was asked:
wood blocks
for i = 1,2.
wood blocks
minimum number of
【在 d****n 的大作中提到】
: This question can be asked in various forms, here is the one I was asked:
: A carpenter is trying to build some furniture, he need a list wood blocks
: with different length, say L1, L2, ... Ln where 1 <= Li <= LMAX for i = 1,2.
: . n. He need to purchase whole wood blocks from the shop. The wood blocks
: in the shop are fixed length, say LEN, LEN >= LMAX.
: Can you help the carpenter save money by figuring out the minimum number of
: whole wood blocks he need to purchase?
: Any idea on how to solve this?
| c*******L
发帖数: 125 | 3 bin packing
NP complete
2.
blocks
of
【在 d****n 的大作中提到】
: This question can be asked in various forms, here is the one I was asked:
: A carpenter is trying to build some furniture, he need a list wood blocks
: with different length, say L1, L2, ... Ln where 1 <= Li <= LMAX for i = 1,2.
: . n. He need to purchase whole wood blocks from the shop. The wood blocks
: in the shop are fixed length, say LEN, LEN >= LMAX.
: Can you help the carpenter save money by figuring out the minimum number of
: whole wood blocks he need to purchase?
: Any idea on how to solve this?
| x******3
发帖数: 245 | 4 我觉得这道题不像背包问题，
如果是从一组不定长的木材中选出最少的来拼成给定长，那肯定是背包问题 | d****n
发帖数: 233 | 5 xbeast23 is right, it asks how to use 最少的定长to cover all 不定长的木材.
Anybody has a link for solutions?
【 在 xbeast23 (xbeast23) 的大作中提到: 】 | s*********s
发帖数: 318 | 6 DP?
Min(K) = Min (K1) + Min(K2), where K1+k2=K | Y*****y
发帖数: 361 | 7 This is exactly the classic bin packing problem. I guess the one we have
seen mostly is another variant of this problem.
See here http://en.wikipedia.org/wiki/Bin_packing_problem | B*****t
发帖数: 335 | 8 子集和，整数划分，装载等问题都是0-1背包问题的变形, 这些都是NPC的，一般情况下
没有
什么多项式的解法可以得到最优解。
lz给出的这类装载问题有很多近似解法，比较popular的是O(NlogN)的。如果要得到最优
解可以用回溯+二分，复杂度O(N^N*logN), 看着N^N比较可怕，不过加入剪枝后运算起来
还是比较快的。
【在 x******3 的大作中提到】
: 我觉得这道题不像背包问题，
: 如果是从一组不定长的木材中选出最少的来拼成给定长，那肯定是背包问题
| x******3
发帖数: 245 | 9 能说下这道题用DP怎么解吗， 多谢啦
最优
起来
【在 B*****t 的大作中提到】
: 子集和，整数划分，装载等问题都是0-1背包问题的变形, 这些都是NPC的，一般情况下
: 没有
: 什么多项式的解法可以得到最优解。
: lz给出的这类装载问题有很多近似解法，比较popular的是O(NlogN)的。如果要得到最优
: 解可以用回溯+二分，复杂度O(N^N*logN), 看着N^N比较可怕，不过加入剪枝后运算起来
: 还是比较快的。
|
|
