はじめに
ナップサック問題は、組み合わせ最適化の代表的な問題のひとつです。
今回の記事では、ナップサック問題の基本概念、動的計画法（DP）を用いた解法、そしてRubyを使った実装例を紹介します。
また、限られた個数のアイテムを効率的に扱うための「二分法分割」というテクニックにも触れていきます。
ナップサック問題の概要
ナップサック問題は、限られた重さや容量の中で、与えられたアイテム群のうち価値の総和を最大にするアイテム選択問題としてよく知られています。
今回取り扱うナップサック問題の詳細
少しアレンジしたバージョンとして、複数種類のアイテムを使って、指定された合計金額 x 円を正確に支払う場合の、使用したアイテムの重さの合計をできるだけ大きくする という最適化問題とします。
つまり、単に支払えるかどうかではなく、「支払う際に選んだアイテムの重さの合計が最大になる」組み合わせを求めるのが目的です。
もし、どの組み合わせでも合計金額 x 円を正確に作れない場合は、結果として -1 を出力します。
アイテムの情報
各アイテムは以下の3つの情報を持っています。
- 額面（value）
→ このアイテムを使うと支払える金額の単位です。 - 重さ（weight）
→ このアイテムを使うことで「加算される重さ」の値です。 - 個数（count）
→ そのアイテムが利用可能な個数です。
たとえば、あるアイテムが [value, weight, count] = [3, 4, 2] であれば、
- 額面： 3円ずつ支払える
- 重さ： 4の重さがある
- 個数： 最大2個使える
という意味になります。
入力の形式
入力は以下の形式で与えられます。
最初の行：
n x
- n はアイテムの種類数
- x は正確に支払いたい合計金額
次の n 行：
value weight count
各行には3つの整数がスペース区切りで与えられ、それぞれがそのアイテムの情報（額面・重さ・個数）を表します。
問題例
例えば、以下のような入力が与えられたとします。
3 10
3 4 2
2 3 3
5 6 1
1行目:
- アイテムの種類数 n = 3
- 支払う合計金額 x = 10 円
2行目:
- 1つ目のアイテム: 額面3円、重さ4、使える個数は2個
3行目:
- 2つ目のアイテム: 額面2円、重さ3、使える個数は3個
4行目:
- 3つ目のアイテム: 額面5円、重さ6、使える個数は1個
この場合、各アイテムをどのように組み合わせれば、合計で10円になり、その際の使用アイテムの重さの合計が最大になるかを求めます。
もし、どの組み合わせでも10円にできなければ -1 を出力します。
実装例（Ruby）
# 入力を受け取る
# n : アイテムの種類数, x :支払う合計金額
n, x = gets.split.map(&:to_i)
# 各アイテムについて、額面 value, 重さ weight, 個数 count を受け取る
items = Array.new(n) do
gets.split.map(&:to_i) # [value, weight, count]
end
# dp[i] は「ちょうど i 円を支払ったときの、使用したアイテムの重さの合計の最大値」
# 支払えない金額は -1 として初期化
dp = Array.new(x + 1, -1)
dp[0] = 0 # 0 円の場合は重さ 0
# 各アイテムごとに処理を行う
items.each do |value, weight, count|
# 二分法分割により、個数制限付きアイテムを複数の0-1アイテムに分解
k = 1
split_items = [] # 分解後の (合計value, 合計weight) の組を格納する配列
while count > 0
take = [k, count].min
split_items << [value * take, weight * take]
count -= take
k *= 2
end
# 分解された各アイテムを使って0-1ナップサックの更新を行う
split_items.each do |v_sum, w_sum|
x.downto(v_sum) do |cur|
if dp[cur - v_sum] != -1
dp[cur] = [dp[cur], dp[cur - v_sum] + w_sum].max
end
end
end
end
# もし x 円を支払えなかった場合は -1 を出力、可能ならそのときの最大重量を出力
puts dp[x]
アルゴリズムの詳細
今回の問題は、「動的計画法（DP）」と「0-1ナップサック問題」への変換によって解くことができます。
DP配列dp[x]という配列を「ちょうどx円を支払ったときに得られる、使用したアイテムの重さの合計の最大値」と定義し、初期状態では支払えない金額は -1 で表現します。
また、0 円の場合は何も使わず重さ 0 となるため、dp[0] = 0 とします。
各アイテムについては、枚数制限付きナップサック問題となるため、直接ループすると計算量が大きくなります。
そこで、二分法分割（binary splitting）という手法を用いて、個数制限付きのアイテムを「0-1 ナップサック問題」に変換し、高速化を図ります。
例えば、個数が 13 のアイテムは二分法分割によって 1, 2, 4, 6 といったグループに分割できます（1+2+4+6 = 13）。
分割後は、それぞれのグループを通常の 0-1 ナップサックとしてDP配列を更新していきます。
動的計画法（DP）
動的計画法は、難しい問題を「小さな部分問題」に分けて、それぞれの答えをメモ（記憶）しながら全体の答えを求める方法です。
具体例として、例えば階段を上る方法を考えます。
- 階段が1段なら「1通り」
- 2段なら「1段ずつ上る方法」と「2段で上る方法」の2通り
そして、n段目に到達する方法は、n-1段目とn-2段目の方法の数を足したものになるという規則があることに気づけます。
例えば n = 4 の場合、3段目に到達する方法と、２段目に到達する方法の数を足したものが、４段目に到達する方法の数になるということです。
こうして、一番小さな段（例えば、0段目や1段目）の答えから順に計算していく方法が、動的計画法の考え方です。
0-1ナップサック問題
ナップサック問題と0-1ナップサック問題の違いを簡単に説明します。
ナップサック問題
ナップサック問題は、限られた重さや容量の中で、価値を最大にするアイテムを選ぶ問題です。
具体例として、例えばあなたがリュックサックを持っていて、中に入れられる荷物の重さが決まっているとします。
お菓子や文房具、本など、いくつかのアイテムがあり、それぞれ重さと「価値」（たとえば、おいしさや必要度）が決まっています。
この中から、リュックサックに入れられるように、価値が最大になる組み合わせを選ぶ、という問題がナップサック問題です。
0-1ナップサック問題
「0-1」というのは、各アイテムを「入れる」か「入れない」かのどちらかだけというルールを表します。
0 は「そのアイテムは選ばない」
1 は「そのアイテムは一回だけ選ぶ」
つまり、同じアイテムを何度も入れることはできません。
具体例として、もしお菓子が1つだけあり、「入れるか入れないか」の選択である場合、複数回選んで「2つ以上入れる」ということはできません。
この場合、各アイテムは使うか使わないかの二択なので、問題の名前に「0-1」がついています。
ナップサック問題と0-1ナップサック問題の違い
ナップサック問題には、個数制限付きの問題もあります。
たとえば、あるアイテムが何個もある場合、それぞれを何回も使える（複数回選べる）問題があります。
しかし、0-1ナップサック問題は「各アイテムは一度だけしか使えない」という制約があるため、少しシンプルになります。
どうして0-1ナップサック問題にするの？
ナップサック問題では、アイテムの数が多い場合に計算が難しくなります。
そこで、個数制限がある問題を二分法分割などのテクニックを使って「0-1ナップサック問題」に変換すると、計算しやすくなります。
具体例として、もしあるお菓子が13個あるとします。
直接13回ループするのではなく、「1個」「2個」「4個」「残り6個」のように分割して、それぞれを「入れるか入れないか」で考えれば、効率的に解くことができます。
最後に
今回の記事では、ナップサック問題の一種である「ちょうど x 円支払う場合の最大重量を求める問題」を題材に、動的計画法と二分法分割、0-1ナップサック問題への変換を用いた解法について解説しました。
余談ですが、「ナップザック問題」という記事なども見かけますが、wikiは「ナップサック問題」なのでそちらに合わせています。