Dotaパケットアルゴリズム

今日グループの中の学友は1つのdotaグループのアルゴリズムを書くと言って、つまり1つの配列があって、配列の中の要素は彼の各同僚の戦闘力で、どんなアルゴリズムが彼らを戦闘力によってできるだけ2つのグループに分けることができますかを聞きます.最初はよく考えていませんでしたが、dotaはせいぜい10人だと思います.列挙しても長くはかかりませんが、その後、グループで議論された啓発を受けて、以下の方法を実現しました.

#zdl = [[1, 3, 5, 10000000, 9], [2, 4, 6, 8, 7]].flatten
#zdl = [1,3,5,7,9,100] + [2,4,6,8,11]
zdl = [1, 2, 3, 4, 5, 100, 6, 7, 8, 9, 11]
#zdl = []
#30.times {zdl << rand(100)}
 
def partition arr
  if arr.size.even?
    a, b = arr[0, arr.size / 2], arr[arr.size / 2, arr.size / 2]
  else
    a, b = arr[0, arr.size / 2], arr[arr.size / 2, arr.size / 2 + 1]
    if a.inject(&:+) <= b.inject(&:+)
      a << b.min
      b.delete_at(b.index(b.min))
    end
  end
  adjust a, b
end
 
def adjust a, b
  sum_a = a.inject &:+
  sum_b = b.inject &:+
  return a, b if sum_a == sum_b
  if sum_a > sum_b
    bigger_group, smaller_group =  a, b
  else
    bigger_group, smaller_group =  b, a
  end
  d_value = (sum_a - sum_b).abs
  ii, jj = nil, nil
  bigger_group.each_with_index do |big_value, i|
    temp_d = d_value
    smaller_group.each_with_index do |small_value, j|
      if big_value > small_value
        if d_value / 2 - (big_value - small_value) < temp_d && d_value / 2 >= (big_value - small_value)
          temp_d = d_value / 2 - (big_value - small_value)
          ii, jj = i, j
        end
      end 
    end
  end
  return bigger_group, smaller_group if ii.nil?
  bigger_group[ii], smaller_group[jj] = smaller_group[jj], bigger_group[ii]
  adjust bigger_group, smaller_group
end


p zdl
a, b = partition zdl

p a
p a.inject &:+
p b
p b.inject &:+

アルゴリズムの構想は、まずそれを勝手に2つのグループに分けて、それから2つのグループの総戦闘力の差を計算して、それから戦闘力の総額の高いグループの中から1つの戦闘力を取って、戦闘力の低いグループの中から1つの値を減らして、もしこの2つの値の差がちょうど2つのグループの差に等しいならば、交換した後に総戦闘力は等しいです.このような値がなければ、最も近いものを交換し、その後、交換後の2組の戦闘力を再帰する.