团队生成器的算法

Question

我创建了一个带有Javascript的随机团队生成器，它可以生成两个随机的团队，每个队有5名球员。这就是它的样子：

​

我创建了一个函数来确定每个级别的值：

function getRankValue(rank) {
let rankValue;

    switch(rank) {
        case "platinum1" : rankValue = 2100;
        break;

        case "platinum2" : rankValue = 2000;
        break;

        case "platinum3" : rankValue = 1900;
        break;

        case "platinum4" : rankValue = 1800;
        break;

        case "gold1" : rankValue = 1650;
        break;

        case "gold2" : rankValue = 1550;
        break;

        case "gold3" : rankValue = 1450;
        break;

        case "gold4" : rankValue = 1350;
        break;

        case "silver1" : rankValue = 1200;
        break;

        case "silver2" : rankValue = 1100; 
        break;

        case "silver3" : rankValue = 1000;
        break;

        case "silver4" : rankValue = 900;
        break;

        case "bronze1" : rankValue = 750;
        break;

        case "bronze2" : rankValue = 650; 
        break;

        case "bronze3" : rankValue = 550;
        break;

        case "bronze4" : rankValue = 450;
        break;

        case "iron1" : rankValue = 300;
        break;

        case "iron2" : rankValue = 200;
        break;

        case "iron3" : rankValue = 100;
        break;

        case "iron4" : rankValue = 0;
        break;
    }

    return rankValue;

我想让生成器创建基于球员排名价值的团队，以创造一个平衡的团队总价值。例如：

4x Silver4(每个900值)和1x青铜4 (450值)，总价值为4050，而不是：

3x Silver1(每个1200值)和2x iron2(各200个值)，总价值为4000。我想让它有一些空间给+- 200值，否则就太复杂了。

算法应该是什么样的呢？

Answer 1

下面是一个基于生成所有组合的解决方案。请注意，平衡数划分和双向分割有许多实用的解决方案。这里给出的解决方案使用了对所有5名球员组合的蛮力评估。

使用python组合函数作为参考，下面的combinations迭代器函数的Javascript版本从提供的10名玩家列表中生成5名玩家的组合。整体解决方案是蛮力，它迭代所有组合的5名球员，并返回最佳组合的球员基础上最小的球队价值。

​

function *combinations( combo, list, k ) {
  if ( k == 0 ) {
    yield combo;
  } else {
    for ( let i = 0; i < list.length; i++ ) {
      yield *combinations( [...combo, list[ i ] ], list.slice( i + 1 ), k - 1 ); 
    }
  }
}


let players = [ 1200, 1200, 1200, 900, 900, 900, 900, 450, 200, 200 ];
let playersTotal = players.reduce( ( sum, player ) => sum += player, 0 );

let team1 = combinations( [], players, 5 );

let nextCombo;
let minCombo, minDiff = Number.MAX_SAFE_INTEGER;

do {
  nextCombo = team1.next().value;
if ( nextCombo == null ) break;
  let team1Sum = nextCombo.reduce( ( sum, player ) => sum += player, 0 );
  let diff = Math.abs( ( playersTotal - team1Sum ) - team1Sum );
  if ( diff < minDiff ) {
    minCombo = nextCombo;
    minDiff = diff;
  }
  if ( diff <= 200 ) {
    console.log( `Team: ${nextCombo.join( ',' )}, Total: ${team1Sum}, Diff: ${diff}` );
  }
} while ( true );

console.log( `Best matchup is Team 1 of ${minCombo} with diff of ${minDiff}` );

​

注意，如果对最近的结果满意，使用迭代器函数生成组合具有终止对进一步组合的请求的优点。这也有一个好处:如果搜索更大的团队，而在其中计算所有组合是不实际的，则可以在循环中添加一个计时器来获取下一个团队组合，并且在计时器结束后可以使用最好的结果，从而限制搜索时间。在这种情况下，谨慎的做法是在调用combinations之前随机地洗牌玩家列表，这样生成的组合不会都被最好的球员重载，从而给出更好的机会获得均衡的团队配对。