Dota分组算法

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

#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 楼 piecehealth 2013-09-14  

kljjack 写道

如果两个人的战斗力差等于两组的战斗力和差，互换两人，总战斗力怎么就相等了？互换两人之后，两人的战斗差值还不是等于两组战斗力和差值的绝对值！

是的，后来加了更多的测试数据，因为这点出现了bug，把25行改为temp_d = d_value / 2就可以了。应该是两人战斗力差值等于（或者最接近于）队伍差值的1 / 2才互换。

1 楼 kljjack 2013-09-14  

如果两个人的战斗力差等于两组的战斗力和差，互换两人，总战斗力怎么就相等了？互换两人之后，两人的战斗差值还不是等于两组战斗力和差值的绝对值！