ナップサック問題？

某プログラム勉強会で、お題が出たので解いてみる。

あなたは硬貨を何枚か持っており、ある金額を払いたい。

お釣りの金額が最小となるような硬貨の組み合わせと、その場合のおつりを計算せよ。

硬貨の価値はすべて正の整数、払いたい金額も正の整数で、オーバーフローは考慮しなくても良いとする。

最良の組み合わせが複数ある場合、そのうちひとつを出力すればよい。 

問題を読んだ瞬間「ナップサック問題？」と思ったけれど微妙に違う。
しかし、「持っている硬貨の金額合計−払う金額」を超えない最大硬貨の組み合わせと考えるとナップサック問題になる。
ナップサック問題の解法はネットにいくらでもあるし楽勝楽勝。と思っていた・・が。
よく見かける動的計画法を使ったアルゴリズムは同じ硬貨を何枚でも使っていい場合のみ適用できるので、この問題では使えない。
その他は遺伝的アルゴリズムとか必ずしも最適解を出すとは限らないものばかり。さすがＮＰ困難の問題。

結局力技で解決。
コインの全ての組み合わせを生成してるので（多少枝狩りはしているが）コインの種類が多くなると遅くなる。

class Coins
  def initialize(total, coins)
    @total = total
    @coins = coins
  end

  def gen_sum(coins)
    if coins.size == 1
      @used.push coins.first
      yield coins.first
      @used.pop
      yield 0
    else
      car,*cdr = coins
      gen_sum(cdr) do |sum|
        next if sum > @sum_limit
        yield sum
        next if car + sum > @sum_limit
        @used.push car
        yield car + sum
        @used.pop
      end
    end
  end

  def solve
    @used = []
    used_sv = nil
    min = @coins.first
    @sum_limit = @total + min - 1
    gen_sum(@coins) do |sum|
      change = sum - @total
      next if change < 0
      if change < min
        min = change
        used_sv = @used.clone
      end
      break if min == 0
    end
    puts "金額 : %d,  支払い : %s,  おつり : %d"%[@total, used_sv.sort.inspect, min]
  end
end

total, *coins = ARGV.map(&:to_i)
Coins.new(total, coins.sort).solve