S*********1
发帖数: 3004 | 1 47个item，让你从中选6个，这6个Item加起来，就是所有的a加到一起等于（最接近）
某个值，b加到一起等于（或者最近接）某个值......一直到e加到一起等于(或者最接
近）某个值，问你如何挑选这6个item？
47 每个item都对应一组数（a－e五个值）
如果需要实际数据，我可以发给你。
我是读社科类方法学的，没什么数学基础。这个非作业，４７个item可以手算，可是实
际问题估计都是成百上千的item，没办法用手算的。包子答谢。 |
s**********o
发帖数: 197 | 2 先从４７个item里减去一个，调整目标，再在４６个里找５个最接近新目标的。
...
最后一步是４２个item里找１个最接近的。 |
S*********1
发帖数: 3004 | 3
这组数据里，我估计手动可以找到，
如果几百个几千个item，手算是不行的哦。
【在 s**********o 的大作中提到】
: 先从４７个item里减去一个，调整目标，再在４６个里找５个最接近新目标的。
: ...
: 最后一步是４２个item里找１个最接近的。
|
P****a
发帖数: 864 | 4 一看来讲，2个是O(n),三个O(n^2),我怀疑是不是6个要O(n^5)
【在 S*********1 的大作中提到】
:
: 这组数据里，我估计手动可以找到，
: 如果几百个几千个item，手算是不行的哦。
|
k**********g
发帖数: 989 | 5 nchoosek(47, 6) = 10737573
一千萬個組合是可以讓電腦窮舉做測試的，估計不到一秒完成。
http://en.wikipedia.org/wiki/Binomial_coefficient
上千個item看來很難搞。 |
w***n
发帖数: 1084 | 6 Let x_0, x_1, ..., x_5 be an initial set of your solution (x_i \in [1..N])
let the error metric be:
E=|a(x_0)+a(x_1)+... - C_a|^2+|b(x_0)+b(x_1)+... - C_b|^2...
while /*loop until you cannot get any improvement*/
for any i in [0, 1, 2, 3, 4, 5]
if you can find a new x_i that improves your error metric E
replace x_i by the new x_i
end of while
This is an iterative method.
Each iteration uses O(N) time.
It is guaranteed to converge.
In each iteration, you try to find the best solution for x_i, given the current set.
But you may end up with a local minimum. The local minimum is sensitive to your initial guess, so try several random guesses and pick a best solution.
Or you may just use simulated annealing, which jumps among random sets at the beginning. |
c*****l
发帖数: 879 | |
S*********1
发帖数: 3004 | 8
您给解释下撒
【在 c*****l 的大作中提到】
: 背包问题
|
h********8
发帖数: 7355 | 9 可能我太懒，（或太笨）， 觉得４７个items也得用computer。。。
把所有items放进２dimention array
loop thru a to e
sort by a（or b，c，d，e）， ascending，找出item n，其a＞a＿sum６
把item １－ n 放进新２dimention array，砍去其它items（a太大）。
end loop
剩下的２dimention array回小很多
穷算之，找到６个items。
【在 S*********1 的大作中提到】
: 47个item，让你从中选6个，这6个Item加起来，就是所有的a加到一起等于（最接近）
: 某个值，b加到一起等于（或者最近接）某个值......一直到e加到一起等于(或者最接
: 近）某个值，问你如何挑选这6个item？
: 47 每个item都对应一组数（a－e五个值）
: 如果需要实际数据，我可以发给你。
: 我是读社科类方法学的，没什么数学基础。这个非作业，４７个item可以手算，可是实
: 际问题估计都是成百上千的item，没办法用手算的。包子答谢。
|
G***s
发帖数: 10030 | 10
其实我还是不太懂。不过有版上同学帮我解了。
谢谢。
【在 h********8 的大作中提到】
: 可能我太懒，（或太笨）， 觉得４７个items也得用computer。。。
: 把所有items放进２dimention array
: loop thru a to e
: sort by a（or b，c，d，e）， ascending，找出item n，其a＞a＿sum６
: 把item １－ n 放进新２dimention array，砍去其它items（a太大）。
: end loop
: 剩下的２dimention array回小很多
: 穷算之，找到６个items。
|
j*****j
发帖数: 201 | 11 这是标准的subset sum problem. NP-complete的。
网上能找到些heuristic algorithm，上规模基本不可能很快算出来的
【在 S*********1 的大作中提到】
: 47个item，让你从中选6个，这6个Item加起来，就是所有的a加到一起等于（最接近）
: 某个值，b加到一起等于（或者最近接）某个值......一直到e加到一起等于(或者最接
: 近）某个值，问你如何挑选这6个item？
: 47 每个item都对应一组数（a－e五个值）
: 如果需要实际数据，我可以发给你。
: 我是读社科类方法学的，没什么数学基础。这个非作业，４７个item可以手算，可是实
: 际问题估计都是成百上千的item，没办法用手算的。包子答谢。
|
l******e
发帖数: 470 | 12 恩，就这么大点数据就穷举就行。
【在 k**********g 的大作中提到】
: nchoosek(47, 6) = 10737573
: 一千萬個組合是可以讓電腦窮舉做測試的，估計不到一秒完成。
: http://en.wikipedia.org/wiki/Binomial_coefficient
: 上千個item看來很難搞。
|
