一个算法问题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Programming - 葵花宝典

一个算法问题

一个算法问题# Programming - 葵花宝典

S*s2007-02-04 08:02

1 楼

有m块石头，每块石头的重量已知，有可能有几块石头的重量相等。选择一些石头装进
背包，这样背包一共最多可能有2^m个可能的重量。把这些重量排序，第n个重量是多少？
由于组合数爆炸，把所有可能穷举再排序是不可行的。

l*t2007-02-04 08:02

2 楼

what is your definition of nth weight ?

少？

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

: 有m块石头，每块石头的重量已知，有可能有几块石头的重量相等。选择一些石头装进
: 背包，这样背包一共最多可能有2^m个可能的重量。把这些重量排序，第n个重量是多少？
: 由于组合数爆炸，把所有可能穷举再排序是不可行的。

S*s2007-02-04 08:02

3 楼

sort the 2^m weights, then you know 1th, 2th, .... 2^m th weights.

t*t2007-02-04 08:02

4 楼

我说个idea,是求前n个重量的,可能对只求第n个不是最优
把石头重量排序.保留一个长n的排序队列,每次把这n个重量加进第i块石头变成2n个重
量,合并后保留前n个.复杂度是mlogm+n*m

少？

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

S*s2007-02-04 08:02

5 楼

u only reserve 前n个in each merge. r u sure those in the rest n won't be
promoted to front n combining with i+1 stone?

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

: 我说个idea,是求前n个重量的,可能对只求第n个不是最优
: 把石头重量排序.保留一个长n的排序队列,每次把这n个重量加进第i块石头变成2n个重
: 量,合并后保留前n个.复杂度是mlogm+n*m
:
: 少？

t*t2007-02-04 08:02

6 楼

因为你石头的重量是(从小到大)排序的.
如果x1排不到前n,那么x1+a肯定也排不上前n,所以x1就可以被删掉
自己模拟一下就知道了,写证明太麻烦

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

: u only reserve 前n个in each merge. r u sure those in the rest n won't be
: promoted to front n combining with i+1 stone?

S*s2007-02-04 08:02

7 楼

still not convincing. say, why keep the front 1/2, instead of 1/4?
i can see you tried to use some idea from dynamic planning. a good direction
. however, to keep n in the queue is still expensive, anyway to get off more
weight?

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

: 因为你石头的重量是(从小到大)排序的.
: 如果x1排不到前n,那么x1+a肯定也排不上前n,所以x1就可以被删掉
: 自己模拟一下就知道了,写证明太麻烦

t*t2007-02-04 08:02

8 楼

很容易理解保留n是下限,因为有可能后面的石头都重量极大,一个就顶前面所有石头的
和,这样的情况下如果多扔掉一个就不对了.保留n当然也是上限,理解见上一篇.
这个肯定是对的,我以前写过一个paper曾经用到这个算法,也有证明.当然我不能证明它
的最优的.

direction
more

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

: still not convincing. say, why keep the front 1/2, instead of 1/4?
: i can see you tried to use some idea from dynamic planning. a good direction
: . however, to keep n in the queue is still expensive, anyway to get off more
: weight?

P*t2007-02-04 08:02

9 楼

石头不用排序也成吧！

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

t*t2007-02-04 08:02

10 楼

我有点不太记得为什么要排序了,好象不排序是也行...?
不过如果n
【在 P***t 的大作中提到】

: 石头不用排序也成吧！

P*t2007-02-04 08:02

11 楼

oh, that makes sense...

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

: 我有点不太记得为什么要排序了,好象不排序是也行...?
: 不过如果n

t*t2007-02-04 08:02

12 楼

不过好象不是基于这个理由.理由是什么呢,我也忘了...嗯,看来要对paper做一下修正.
..

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

: oh, that makes sense...

s*d2007-02-04 08:02

13 楼

Set = { 0(all) stone weight}
for (int i=1; i{
get the ith smallest(largest) weight of the set;
add(remove) one stone to(from) this weight, there are less than m new
weights;
add these weights to the set;
}
the nth smallest(largest) weigh of all combination is the same as
the nth smallest(largest) weight of the set.

b*e2007-02-04 08:02

14 楼

You want to sort it because in each pass, you can do a merging easily to get
n smallest out of two *sorted* n length list. Otherwise, it's a hassle.
Of course, once you sort it, whichever stone you add first it not important.