Dota分组算法_Ruby_编程开发_程序员俱乐部

今天群里的同学说要写一个dota分组算法，即有一个数组，数组里面的元素是他各个同事的战斗力，问有没有什么算法能将他们按战斗力尽可能的分成两组。开始我没有很好地想法，想dota最多十个人，用枚举也不会太久，不过后来受群里讨论的启发，实现了如下方法：

class="ruby" name="code">
zdl = [1,2,3,4,5,6,7,8,9,10000000]
# zdl = [1,2,3,4,5,6,7,8,9,10]

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]
  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 - (big_value - small_value) < temp_d && d_value > (big_value - small_value)
          temp_d = d_value - (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 partition zdl

算法的思路是先将其随便分成两组，然后计算两组总战斗力的差，再从战斗力总值高的一组中取一个战斗力，减去从战斗力低的一组中一个值，如果这两个值的差值正好等于两组的差，互换后总战斗力就相等了。如果没有这样的值，那交换一个最接近的，之后再递归交换后的两组战斗力。