算法分裂值成組，使用等於相同數量的值

組

可以說我有具有N的陣列（在這個例子中N = 10）的值，每個值是1-10之間：算法分裂值成組，使用等於相同數量的值

現在，我想把它們分成P組（對於這個例子P = 2），所有的組都將是偶數（也就是它們的SUM），或者儘可能接近。

我已經寫了一個算法：

public static void mainLogic(ArrayList<Player> team) { 

    Player currentPlayer = new Player(); 
    Player minDifPlayer = new Player(); 

    double minDiff = 100; 

    for (int ind = 0; ind < team.size(); ind++) { 
     if (team.isEmpty()) 
      return; 
     double temp = team.get(ind).get_playeroverall(); 

     if (ind == team.size() - 1) { 
      //if num of Player match for two teams 
      if (team.size() < 18) { 

       // if the teams are equals or teamA AVG small then teamB 
       if (sum(teamA) <= sum(teamB)) { 
        teamA.add(currentPlayer); 
        teamB.add(minDifPlayer); 
        Results.TempArray.add(currentPlayer); 
        Results.TempArray.add(minDifPlayer); 
        team.remove(currentPlayer); 
        team.remove(minDifPlayer); 
        //if teamB AVG small then teamA 
       } else if (sum(teamA) > sum(teamB)) { 
        teamB.add(currentPlayer); 
        teamA.add(minDifPlayer); 
        Results.TempArray.add(currentPlayer); 
        Results.TempArray.add(minDifPlayer); 
        team.remove(currentPlayer); 
        team.remove(minDifPlayer); 
       } 
       // if the teams are full, Player are subscribed to the following team 
       if (teamA.size() == 6 && teamB.size() == 6) { 
        teamC.addAll(team); 
        Results.TempArray.addAll(team); 
        team.clear(); 
       } 

       ind = 0; 
       minDiff = 100; 
       if (!team.isEmpty()) 
        temp = team.get(ind).get_playeroverall(); 
      } 
     } 
     for (int pointer = ind + 1; pointer <= team.size() - 1; pointer++) { 

      double rankToCompare = team.get(pointer).get_playeroverall(); 

      if (Math.abs(temp - rankToCompare) < minDiff) { 
       minDiff = Math.abs(temp - rankToCompare); 
       currentPlayer = team.get(ind); 
       minDifPlayer = team.get(pointer); 
      } 
     } 
    } 
}

的問題是，該算法並沒有完全解決。對於同上面的例子，他給了我

10  8.4 
7.8  7.9 
7.3  7.3 
6.9  7.7 
5.8  6.1 
SUM=37.8 SUM=37.4

，我可以手動這種方式更好匹配他們：

10  8.4 
7.7  7.9 
7.3  7.3 
6.9  7.8 
5.8  6.1 
SUM=37.7 SUM=37.5

（我寫的目的是到3組，每組6名選手的算法 - 意味着18名球員頂部，當額外的球員移動到以下組）

來源

2017-09-29 GuyShoham

您發佈的問題是一個NP難題，它被稱爲計算機科學中的K方式分區問題。

這個問題很少有近似解決方案和貪婪解決方案。

因爲它是一個衆所周知的理論問題，我建議你去看看Partitioning Problem。

來源

2017-09-29 18:26:32

我看看你的鏈接，其中沒有一個（甚至是貪婪的解決方案）的不給我最佳的解決方案 '這貪婪的方法被稱爲給予7/6，近似的最優解優化版本' 我提醒你我需要相同數量的值每邊以及 – GuyShoham

是的，他們不會給你最佳的解決方案。這就是NP-Hard下的近似算法的全部要點。獲得最佳解決方案的唯一方法是進行徹底搜索。像組合所有可能的組合。這就是爲什麼它是Np-Hard。您可能無法在多項式時間內解決此問題 –

非常感謝！你幫了我很多，現在我有更多的線索如何從這裏開始 – GuyShoham

算法分裂值成組，使用等於相同數量的值

回答

相關問題