1<<-DOC
  2You have a collection of coins, and you know the values of the coins and the quantity of each type of coin in it.
  3You want to know how many distinct sums you can make from non-empty groupings of these coins.
  4
  5Example
  6
  7For coins = [10, 50, 100] and quantity = [1, 2, 1], the output should be
  8possibleSums(coins, quantity) = 9.
  9
 10Here are all the possible sums:
 11
 1250 = 50;
 1310 + 50 = 60;
 1450 + 100 = 150;
 1510 + 50 + 100 = 160;
 1650 + 50 = 100;
 1710 + 50 + 50 = 110;
 1850 + 50 + 100 = 200;
 1910 + 50 + 50 + 100 = 210;
 2010 = 10;
 21100 = 100;
 2210 + 100 = 110.
 23As you can see, there are 9 distinct sums that can be created from non-empty groupings of your coins.
 24
 25Input/Output
 26
 27[time limit] 4000ms (rb)
 28[input] array.integer coins
 29
 30An array containing the values of the coins in your collection.
 31
 32Guaranteed constraints:
 331 ≤ coins.length ≤ 20,
 341 ≤ coins[i] ≤ 104.
 35
 36[input] array.integer quantity
 37
 38An array containing the quantity of each type of coin in your collection. quantity[i] indicates the number of coins that have a value of coins[i].
 39
 40Guaranteed constraints:
 41quantity.length = coins.length,
 421 ≤ quantity[i] ≤ 105.
 43
 44It is guaranteed that (quantity[0] + 1) * (quantity[1] + 1) * ... * (quantity[quantity.length - 1] + 1) <= 106.
 45
 46[output] integer
 47
 48The number of different possible sums that can be created from non-empty groupings of your coins.
 49DOC
 50
 51describe "#possible_sums" do
 52  def possible_sums(coins, quantity)
 53    maximum = coins.zip(quantity).map { |(x, y)| x * y }.sum
 54
 55    dp = [false] * (maximum + 1)
 56    dp[0] = true
 57
 58    coins.zip(quantity).each do |(coin, q)|
 59      (0...coin).each do |b|
 60        num = -1
 61        (b..maximum + 1).step(coin).each do |i|
 62          if dp[i]
 63            num = 0
 64          elsif num >= 0
 65            num += 1
 66          end
 67          dp[i] = (0 <= num && num <= q)
 68        end
 69      end
 70    end
 71    dp.map { |x| x ? 1 : 0 }.sum - 1
 72  end
 73
 74  def possible_sums(coins, quantity)
 75    results = { 0 => true }
 76    coins.zip(quantity).each do |coin, number_of_coins|
 77      results.keys.each do |key|
 78        1.upto(number_of_coins) do |n|
 79          results[key + (coin * n)] = true
 80        end
 81      end
 82    end
 83    results.size - 1
 84  end
 85
 86  [
 87    { coins: [10, 50, 100], quantity: [1, 2, 1], x: 9 },
 88    { coins: [10, 50, 100, 500], quantity: [5, 3, 2, 2], x: 122 },
 89    { coins: [1], quantity: [5], x: 5 },
 90    { coins: [1, 1], quantity: [2, 3], x: 5 },
 91    { coins: [1, 2], quantity: [50000, 2], x: 50004 },
 92    { coins: [1, 2, 3], quantity: [2, 3, 10000], x: 30008 },
 93    { coins: [3, 1, 1], quantity: [111, 84, 104], x: 521 },
 94    { coins: [1, 1, 1, 1, 1], quantity: [9, 19, 18, 12, 19], x: 77 },
 95  ].each do |x|
 96    it do
 97      expect(possible_sums(x[:coins], x[:quantity])).to eql(x[:x])
 98    end
 99  end
100end