卖酒的算法题解

基友发来一道算法题：

大概的意思就是：一共有六桶酒，白酒数量为5，上午卖了2，下午还剩3。因此下午三桶的升数之和应该是上午的两倍：

• afternoon = morning * 2

找到这样的关系以后，那么最后剩下那桶就是红酒了。大概想了下，一个比较直接的思路就是，可以把它当成是一个排列组合的任务：上午卖两桶，就是从5个元素里面任意取两个元素；下午卖三桶，就是在剩下的四桶里面任意取3。然后在这样的排列组合当中，找到下午的数字之和是上午的二分之一的组合，然后最后剩下的那个元素就是红酒了。这个任务可以用 ruby 代码来做做看。 ruby 的 array 有 permutation 的能力，我们可以用用看：

可以看到 permutation 把数组里元素所有可能的顺序组合都列出来了。这个 permutation 方法还支持定制选取元素的数量进行排列：

irb(main):005:0> arr.permutation(2).to_a
=> [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

有了这个方法，我们就可以列出所有酒桶的排列方式了。首先是定义酒桶的数组：

irb(main):006:0> buckets = [30, 32, 36, 38, 40, 62]
=> [30, 32, 36, 38, 40, 62]

然后是取其中两个元素，列出所有的可能性，相当于上午取两桶酒的所有可能：

上面这个排列组合里面，数组的元素是有顺序的，因为是 permutation ，而不是 combination 。 ruby 除了『排列』，也提供了『组合』的功能。下面是 combination(...) 方法：

irb(main):012:0> buckets.combination(2).to_a
=> [[30, 32], [30, 36], [30, 38], [30, 40], [30, 62], [32, 36], [32, 38], [32, 40], [32, 62], [36, 38], [36, 40], [36, 62], [38, 40], [38, 62], [40, 62]]

从上面的结果可以看到顺序不同，元素一样的数组不存在了，只剩下元素不同的数组。上面这个数组代表了『上午卖出的两桶酒』的所有可能。因此，我们针对每一个可能，刨去上面的元素，再从剩下的4个元素里面取3，并列出所有的组合。从一个数组中刨去某些元素的代码如下：

可以看到，使用减号就可以了，剩下的元素是刨去了上午售出的酒。此时在这个数组当中再用 combination(...) 方法，取出三个元素，列出所有组合。然后把三个元素的值相加，如果是上午的两个元素相加的值的两倍，那么剩下的那个元素就是最后剩下的红酒了。因此，两个 for 循环就可以完成上面所讲的逻辑了。完整的代码如下：

buckets = [30, 32, 36, 38, 40, 62]
sold_at_morning = buckets.combination(2).to_a

arr = []
for x in sold_at_morning
  left = buckets - x
  sold_at_afternoon = left.combination(3).to_a
  sum_morning = x.inject(0) { |sum, _x| sum + _x }
  for y in sold_at_afternoon
    sum_afternoon = y.inject(0) { |sum, _y| sum + _y }
    if sum_afternoon.to_f / sum_morning == 2
      puts "morning: #{x} / afternoon: #{y} / red wine: #{buckets - x - y}"
      exit
    end
  end
end

上面的代码就是前面讲的思路的实现，具体用到的一些之前没讲到的技巧包括：

sum_morning = x.inject(0) { |sum, _x| sum + _x }

上面这个block会计算数组的元素之和。

sum_afternoon.to_f / sum_morning == 2

上面的 to_f ，把 sum_afternoon 的数值类型从 int 转化成 float ，这样保证我们计算所得是被整除的。因为两个 int 型数据相除是会取整的，这样结果为 2 的时候不一定是被整除为 2 。运行上面的代码，结果如下：

morning: [30, 36] / afternoon: [32, 38, 62] / red wine: [40]

得到结果是红酒为 40 升的这桶，并给出了上午和下午卖出酒桶的升数。以上是对解题思路的一个记录。

∎