关于对战游戏,队伍匹配的算法问题。
最近要面试一家公司,我刚毕业,没项目经验。得知他们正在开发一款对战游戏,类似dota LOL。 在队伍匹配的时候,需要用到什么算法,能保证快速促成一盘游戏,而且双方的实力接近呢。假设衡量每个人实力的一个数值已经得出,不需考虑。
[解决办法]
对等待时间最长的玩家为种子 用其他的玩家 排序分别插入到 两队中
[解决办法]
partition problem
http://en.wikipedia.org/wiki/Partition_problem
Partition: simple version
bool T[10240];
bool partition( vector< int > C ) {
// compute the total sum
int n = C.size();
int N = 0;
for( int i = 0; i < n; i++ ) N += C[i];
// initialize the table
T[0] = true;
for( int i = 1; i <= N; i++ ) T[i] = false;
// process the numbers one by one
for( int i = 0; i < n; i++ )
for( int j = N C[i]; j >= 0; j)
if( T[j] ) T[j + C[i]] = true;
return T[N / 2];
}