S*******s
发帖数: 13043 | 1 有m块石头，每块石头的重量已知，有可能有几块石头的重量相等。选择一些石头装进
背包，这样背包一共最多可能有2^m个可能的重量。把这些重量排序，第n个重量是多少？
由于组合数爆炸，把所有可能穷举再排序是不可行的。 | l***t
发帖数: 81 | 2 what is your definition of nth weight ?
少？
【在 S*******s 的大作中提到】
: 有m块石头，每块石头的重量已知，有可能有几块石头的重量相等。选择一些石头装进
: 背包，这样背包一共最多可能有2^m个可能的重量。把这些重量排序，第n个重量是多少？
: 由于组合数爆炸，把所有可能穷举再排序是不可行的。
| S*******s
发帖数: 13043 | 3 sort the 2^m weights, then you know 1th, 2th, .... 2^m th weights. | t****t
发帖数: 6806 | 4 我说个idea,是求前n个重量的,可能对只求第n个不是最优
把石头重量排序.保留一个长n的排序队列,每次把这n个重量加进第i块石头变成2n个重
量,合并后保留前n个.复杂度是mlogm+n*m
少？
【在 S*******s 的大作中提到】
: 有m块石头，每块石头的重量已知，有可能有几块石头的重量相等。选择一些石头装进
: 背包，这样背包一共最多可能有2^m个可能的重量。把这些重量排序，第n个重量是多少？
: 由于组合数爆炸，把所有可能穷举再排序是不可行的。
| S*******s
发帖数: 13043 | 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****t
发帖数: 6806 | 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*******s
发帖数: 13043 | 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****t
发帖数: 6806 | 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***t
发帖数: 1006 | 9 石头不用排序也成吧！
【在 t****t 的大作中提到】
: 我说个idea,是求前n个重量的,可能对只求第n个不是最优
: 把石头重量排序.保留一个长n的排序队列,每次把这n个重量加进第i块石头变成2n个重
: 量,合并后保留前n个.复杂度是mlogm+n*m
:
: 少？
| t****t
发帖数: 6806 | 10 我有点不太记得为什么要排序了,好象不排序是也行...?
不过如果n
【在 P***t 的大作中提到】
: 石头不用排序也成吧！
| P***t
发帖数: 1006 | 11 oh, that makes sense...
【在 t****t 的大作中提到】
: 我有点不太记得为什么要排序了,好象不排序是也行...?
: 不过如果n
| t****t
发帖数: 6806 | 12 不过好象不是基于这个理由.理由是什么呢,我也忘了...嗯,看来要对paper做一下修正.
..
【在 P***t 的大作中提到】
: oh, that makes sense...
| s*******d
发帖数: 59 | 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***e
发帖数: 1419 | 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. |
|
