升级到测试版10.8.1 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Apple - 家有苹果

升级到测试版10.8.1

升级到测试版10.8.1# Apple - 家有苹果

m*12012-08-21 07:08

1 楼

正常吧, 有好人也有坏蛋,只愿好人更多些.
由于大部分人心中不知道自己活着是干什么,所以只能以名校等等为自豪.
我面时,也碰到同胞,有的尽最大力当场叫系主任选我; 有的当面说我的研究没深度,他
没而CNS,我有SN; 也有不理不睬的. 总的说来,作梗的多. 其实他们也没自信的,也挺可
悲的.
就象在此版面,有的为自己学生找到教职工或其他好工作,高兴和自豪. 你看版上有无数
的跟帖为他高兴; 所以且宽心,

d*n2012-08-21 07:08

2 楼

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*i2012-08-21 07:08

3 楼

美国这边的信用卡不可以吗？谢谢。

a*y2012-08-21 07:08

4 楼

电池寿命还没有观察
但是蓝牙死机的问题貌似没有了。

A*x2012-08-21 07:08

5 楼

"总的说来,作梗的多"
我听到后很悲观。最近一直抑郁。
我们是怎么了。

B*t2012-08-21 07:08

6 楼

这些都是背包问题变体

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?

k*22012-08-21 07:08

7 楼

您只能使用由中国本地的银行发行的借记卡在网上支付签证费(我们不支援信用卡或在
中国境外发行的借记卡)。如果您没有一个中国本地的借记卡，请选择其他的付款方式
。

c*L2012-08-21 07:08

8 楼

bin packing
NP complete

2.
blocks
of

【在 d****n 的大作中提到】

x*32012-08-21 07:08

9 楼

我觉得这道题不像背包问题，
如果是从一组不定长的木材中选出最少的来拼成给定长，那肯定是背包问题

d*n2012-08-21 07:08

10 楼

xbeast23 is right, it asks how to use 最少的定长to cover all 不定长的木材.
Anybody has a link for solutions?
【在 xbeast23 (xbeast23) 的大作中提到: 】

s*s2012-08-21 07:08

11 楼

DP?
Min(K) = Min (K1) + Min(K2), where K1+k2=K

Y*y2012-08-21 07:08

12 楼

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*t2012-08-21 07:08

13 楼

子集和，整数划分，装载等问题都是0-1背包问题的变形, 这些都是NPC的，一般情况下
没有
什么多项式的解法可以得到最优解。
lz给出的这类装载问题有很多近似解法，比较popular的是O(NlogN)的。如果要得到最优
解可以用回溯+二分，复杂度O(N^N*logN), 看着N^N比较可怕，不过加入剪枝后运算起来
还是比较快的。

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

: 我觉得这道题不像背包问题，
: 如果是从一组不定长的木材中选出最少的来拼成给定长，那肯定是背包问题

x*32012-08-21 07:08

14 楼

能说下这道题用DP怎么解吗，多谢啦

最优
起来

【在 B*****t 的大作中提到】

: 子集和，整数划分，装载等问题都是0-1背包问题的变形, 这些都是NPC的，一般情况下
: 没有
: 什么多项式的解法可以得到最优解。
: lz给出的这类装载问题有很多近似解法，比较popular的是O(NlogN)的。如果要得到最优
: 解可以用回溯+二分，复杂度O(N^N*logN), 看着N^N比较可怕，不过加入剪枝后运算起来
: 还是比较快的。