【Ruby】最小個数部分和問題を動的計画法で解く

1 2 3 4 5

ここにある数字を好きに組み合わせて足していき、目標となる値を作れるか？
そんな問題を「部分和問題」という。

9を目標の数とする場合

1, 3, 5
2, 3, 4
4, 5

目標の数となる組み合わせはいくつかあり、その中でも4, 5が手っ取り早い。
このような
「目標の数を作るために、必要な数の個数は最小で何個か？」
というのを考えるのが「最小個数部分和問題」である。

これを「動的計画法」を用いて効率よく解く方法を解説する。

動的計画法を使う
実装
余談

動的計画法を使う

1. 表を用意する

縦は計算で使用する各要素(i)、横は目標となる値(j)。
"-" の行は、いずれの要素も使用していない時を表す。

	0	1	2	3	4	5	6	7	8	9
-
1
2
3
4
5

2. 初期値を埋める

	1	2	3	4	5	6	7	8	9
-	∞	∞	∞	∞	∞	∞	∞	∞	∞
1
2
3
4
5

各マスの意味は以下の通り。

要素を先頭から i 種使用して、合計 j となる時の最小個数

すると、以下の条件の時の値は、計算せずに求められる。

j = 0

目標の値が0の時は、要素を使わずに作れるため、最小個数も0。

i = 0, j = 1..9(目標の値)

要素を一つも使わずに0より大きな値を作ることはできないため、解なしとして∞を代入。

3. 各マスの計算

	1	2	3	4	5	6	7	8	9
-	∞	∞	∞	∞	∞	∞	∞	∞	∞
1	1	∞	∞	∞	∞	∞	∞	∞	∞
2	1	1	2	∞	∞	∞	∞	∞	∞
3	1	1	1	2	2	3	∞	∞	∞
4	1	1	1	1	2	2	2	3	3
5	1	1	1	1	1	2	2	2	2

i番目の要素をwとしたとき、dp[i + 1][j] の値は以下の通り。

j < w なら

dp[i][j]

j ≧ w なら以下の二つの内、小さい方。

dp[i][j]
dp[i][j - w] + 1

実装

個数制限あり

各要素は一回のみ使用可能なバージョン。

ITEM = [1, 2, 3, 4, 5]

N = ITEM.size
A = 9

memo = Array.new(N + 1) { Array.new(A + 1) }
(0..N).each { |i| memo[i][0] = 0 }
(1..A).each { |i| memo[0][i] = Float::INFINITY }

i = 0
while i < N
  j = 1
  while j <= A
    w = ITEM[i]
    memo[i + 1][j] = (
      if j >= w
        k = memo[i][j]
        l = memo[i][j - w] + 1
        k < l ? k : l
      else
        memo[i][j]
      end
    )

    j += 1
  end 
  i += 1
end

p memo[N][A]

個数制限なし

各要素は何度でも再利用可能なバージョン。

dp[i][j - w] + 1

を

dp[i +1][j - w] + 1

に書き換えただけである。

ITEM = [1, 3, 2, 4]

N = ITEM.size
A = 17

memo = Array.new(N + 1) { Array.new(A + 1) }
(0..N).each { |i| memo[i][0] = 0 }
(1..A).each { |i| memo[0][i] = Float::INFINITY }

i = 0
while i < N
  j = 1
  while j <= A
    w = ITEM[i]
    memo[i + 1][j] = (
      if j >= w
        k = memo[i][j]
        l = memo[i + 1][j - w] + 1
        k < l ? k : l
      else
        memo[i][j]
      end
    )

    j += 1
  end
  i += 1
end

p memo[N][A]

個数制限あり・一次元配列

ループは逆順。

ITEM = [1, 2, 3, 4, 5]
N = ITEM.size
A = 9

memo = Array.new(A + 1, Float::INFINITY)
memo[0] = 0

i = 0
while i < N
  j = A
  while j > 0
    w = ITEM[i]
    if j >= w
      k = memo[j]
      l = memo[j - w] + 1
      memo[j] = k < l ? k : l
    end
    
    j -= 1
  end
  i += 1
end

p memo[A]

個数制限なし・一次元配列

ループは普通順。

ITEM = [1, 3, 4, 2]
N = ITEM.size
A = 17

memo = Array.new(A + 1, Float::INFINITY)
memo[0] = 0

i = 0
while i < N
  j = 0
  while j <= A
    w = ITEM[i]
    if j >= w
      k = memo[j]
      l = memo[j - w] + 1
      memo[j] = k < l ? k : l
    end
    
    j += 1
  end
  i += 1
end

p memo[A]

貪欲法

ITEM = [500, 100, 50, 10, 5, 1]
A = 650

a = A
i = 0
c = 0
s = ITEM.size

while i < s
  c += v = a / ITEM[i]
  a %= ITEM[i]
  i += 1
end

p c

硬貨問題を解く場合、日本の通貨体系であれば、貪欲法でも最小個数が求められる場合がある。
各要素で、隣り合う要素が割り切れる関係にあればいいらしい*1が、もう少し詳しく条件を説明している所があるので、そちらを参照。
(算数が怪しい私にはぶっちゃけよくわからない)

qiita.com

余談

「K個以内部分和問題」というものがある。
部分和問題に個数の制約が加わったものだ。
制約が加わっているために「メモの次元も増やして考えなければいけないのか？」と一瞬思う。
しかし、実際には最小個数部分和問題の解は最適解なので、それをもとに判定すればいい。

今回は5種もコードを書いた挙句よく理解もしてないのでバグ取りが怪しいです。
あったら教えて下さい（丸投げ）

*1:例外として2,000円札はオッケー

地上の洞窟

どこにも行かず、液晶と「にらめっこ」し続ける人の物語。