问题：
假设有m个变量，x1,x2....xm
对于每个变量 xi，都有v个取值，从大到小排列为{ ai1,ai2....aiv}
变量 S=x1+x2+....+xm，求S的所有可能取值中前N大个值

我的想法是：S的最大值一定是 a11+a21+...+am1，状态表示就为{1,1...1}(m个1)，代表所有变量xi都取最大值。
于是可以维护一个优先队列（最大堆优先队列），先将状态{1,1...1}加入队列中，然后每次取出队首，将原状态中的某一变量xj的取值（设为 ajp)改为aj(p+1)，如此便可扩展出m个新状态，加入优先队列中。
反复操作，第N次取出队首之后，便得到了S的前N大个取值。

感觉这样的算法应该是正确的，但是无法证明。不知大家能否证明我的想法是正确的（或错误的），或者有没有其他的方法。

• Re:请教大家一个算法 (390) cg7 2010-01-06 20:29:02
  • Re:请教大家一个算法 (149) cg7 2010-01-06 20:36:13