s*********x
发帖数: 17 | 1 Three treasure hunters need to divide up some trinkets that they have looted
. Assume that the total value of all trinkets is T, and that the value of
each trinket is less than or equal to c. Given a sequence of trinket values
x_1, ..., x_n, partition the trinkets into 3 (disjoint) sets such that the
value of all the trinkets in each set is between T/3 - 2c/3 and T/3 + 2c/3. | l*********y
发帖数: 1431 | 2 你需要生成均值是T/3，方差是2c/3的高斯分布. | s*********x
发帖数: 17 | 3 关键是需要证明这个是正确的。如果用greedy algorithm, 怎么证明这个是正确的。 | l*********y
发帖数: 1431 | | s*********x
发帖数: 17 | 5 Three treasure hunters need to divide up some trinkets that they have looted
. Assume that the total value of all trinkets is T, and that the value of
each trinket is less than or equal to c. Given a sequence of trinket values
x_1, ..., x_n, partition the trinkets into 3 (disjoint) sets such that the
value of all the trinkets in each set is between T/3 - 2c/3 and T/3 + 2c/3. | l*********y
发帖数: 1431 | 6 你需要生成均值是T/3，方差是2c/3的高斯分布. | s*********x
发帖数: 17 | 7 关键是需要证明这个是正确的。如果用greedy algorithm, 怎么证明这个是正确的。 | l*********y
发帖数: 1431 | | h**********g
发帖数: 3962 | 9 Here is a simple greedy algorithm.
Stage-0: Sorting the sequence into non-increasing order.
Therefore we can assume that
x_1 >= x_2 >= ... >= x_n.
Stage-1: Putting the next item into the lightest basket.
We use three baskets: A, B, C, which are initially
empty.
FOR i=1 TO n DO {
put x_i into the lightest basket
}
The proof of correctness is left as an ***individual homework***
for an undergraduate algorithms class.
looted
values
the
【在 s*********x 的大作中提到】
: Three treasure hunters need to divide up some trinkets that they have looted
: . Assume that the total value of all trinkets is T, and that the value of
: each trinket is less than or equal to c. Given a sequence of trinket values
: x_1, ..., x_n, partition the trinkets into 3 (disjoint) sets such that the
: value of all the trinkets in each set is between T/3 - 2c/3 and T/3 + 2c/3.
|
|
