System Note
$ cat /proc/ai-disclosure
本記事の構成および論理分析にはAI（人工知能）を使用しています。情報の正確性は、システム管理者（UNIXユーザー）による手動検証済みです。
【ナップサック問題で遊ぼう】C言語で全探索から動的計画法まで｜定番問題をコードパズルにしてみた | UNIX Cafe
アルゴリズムを学んでいると、よく登場する定番問題に 「ナップサック問題」 があります。
名前だけ聞くと少し難しそうですが、やっていることはとても身近です。重さと価値の違う品物がいくつかあり、ナップサックに入れられる重さには上限があります。その中で、できるだけ価値が高くなるように品物を選ぶ、という小さなパズルです。
今回は、このナップサック問題を C言語 で遊びながら見ていきます。最初は全部の選び方を試す素直な方法から始めて、最後は動的計画法（DP）で効率よく解くところまで進みます。
目次
ナップサック問題ってなに？
本題に入る前に、少しだけ 0/1ナップサック問題 のルールを整理しておきます。
たとえば、次のような品物があるとします。
| 品物 | 重さ | 価値 |
|---|---|---|
| A | 2 | 3 |
| B | 1 | 2 |
| C | 3 | 4 |
| D | 2 | 2 |
ナップサックの容量は 5 です。
このとき、合計の重さが 5 以下になるように品物を選び、その中で価値の合計を最大にします。
- Aを入れる？ 入れない？
- Bを入れる？ 入れない？
- Cを入れる？ 入れない？
- Dを入れる？ 入れない？
ひとつひとつの品物について「選ぶ」か「選ばない」かを決めるので、これは 0/1ナップサック問題 と呼ばれます。同じ品物を何度も入れることはできません。
C言語では、重さと価値を配列で表せます。
int weights[] = {2, 1, 3, 2};
int values[] = {3, 2, 4, 2};
int capacity = 5;
int n = 4;目標は、capacity を超えない範囲で、価値の合計を最大にすることです。
ナップサック問題の基本ルール
今回使うルールを、もう少しゲームっぽく並べるとこうなります。
| ルール | 内容 |
|---|---|
| 品物には重さがある | バッグの容量を超えると失敗 |
| 品物には価値がある | 価値の合計をできるだけ大きくしたい |
| 各品物は1回だけ | 同じ品物を何度も選べない |
| 答えは1つとは限らない | 同じ最大価値になる選び方が複数あることもある |
この「答えが1つとは限らない」というところが、ちょっとパズルらしい部分です。
今回の例では、AとCを選ぶと重さは 2 + 3 = 5、価値は 3 + 4 = 7 になります。
また、A、B、Dを選んでも重さは 2 + 1 + 2 = 5、価値は 3 + 2 + 2 = 7 です。
どちらも容量ぴったりで、価値は 7。つまり、最大価値になる選び方が複数あります。
その1：まずは全部試してみるナップサック（全探索）
まずは一番わかりやすい方法から見てみましょう。
品物が4個なら、それぞれについて「選ぶ」「選ばない」の2通りがあります。つまり、全部で 2 * 2 * 2 * 2 = 16 通りです。
16通りくらいなら、全部試してしまえば答えが出ます。
今回は、まず knapsack_bruteforce.c というファイルを作るイメージで、中心になる関数を見ていきます。
int knapsack_bruteforce(int weights[], int values[], int n, int capacity) {
int best = 0;
for (int mask = 0; mask < (1 << n); mask++) {
int total_weight = 0;
int total_value = 0;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
total_weight += weights[i];
total_value += values[i];
}
}
if (total_weight <= capacity && total_value > best) {
best = total_value;
}
}
return best;
}このコードは、すべての選び方をビットで表して調べています。
関数の引数
int knapsack_bruteforce(int weights[], int values[], int n, int capacity)weights[]: 各品物の重さvalues[]: 各品物の価値n: 品物の数capacity: ナップサックに入れられる最大重量
C言語の配列は、関数に渡すと配列の要素数が自動ではわかりません。そのため、n も一緒に渡しています。
ビットで選び方を表す
for (int mask = 0; mask < (1 << n); mask++) {1 << n は、2 の n 乗を意味します。
品物が n 個あるとき、それぞれの品物について「入れる / 入れない」の2通りがあるので、組み合わせは全部で 2^n 通りあります。
品物が4個なら 16 通りなので、mask は 0 から 15 まで動きます。
| mask | 2進数 | 選び方のイメージ |
|---|---|---|
| 0 | 0000 | 何も選ばない |
| 1 | 0001 | Aだけ選ぶ |
| 3 | 0011 | AとBを選ぶ |
| 5 | 0101 | AとCを選ぶ |
| 15 | 1111 | 全部選ぶ |
各ビットが 1 ならその品物を選び、0 なら選ばない、と考えます。
if (mask & (1 << i)) {
total_weight += weights[i];
total_value += values[i];
}mask & (1 << i) は、i 番目のビットが立っているかどうかを調べています。立っていれば、その品物を選んでいるという意味です。
全探索版の完成コード
#include <stdio.h>
int knapsack_bruteforce(int weights[], int values[], int n, int capacity) {
int best = 0;
for (int mask = 0; mask < (1 << n); mask++) {
int total_weight = 0;
int total_value = 0;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
total_weight += weights[i];
total_value += values[i];
}
}
if (total_weight <= capacity && total_value > best) {
best = total_value;
}
}
return best;
}
int main(void) {
int weights[] = {2, 1, 3, 2};
int values[] = {3, 2, 4, 2};
int n = 4;
int capacity = 5;
int answer = knapsack_bruteforce(weights, values, n, capacity);
printf("最大価値: %d\n", answer);
return 0;
}コンパイルして実行すると、最大価値は 7 になります。
gcc knapsack_bruteforce.c -o knapsack_bruteforce
./knapsack_bruteforce最大価値: 7全探索の弱点
全探索は考え方がとても素直です。ただし、品物の数が増えると組み合わせの数が急激に増えます。
| 品物の数 | 組み合わせ数 |
|---|---|
| 4 | 16 |
| 10 | 1024 |
| 20 | 1,048,576 |
| 30 | 1,073,741,824 |
品物が30個になると、10億通り以上を調べることになります。ここから先は、もう少し賢い方法がほしくなります。
その2：動的計画法（DP）で解く
次に、ナップサック問題の定番解法である 動的計画法（DP） を使います。
DPでは、「ここまでの品物を見たとき、容量がこの重さなら、最大価値はいくつか」という小さな答えを表に保存していきます。
たとえば、dp[i][w] を次のように考えます。
i個目までの品物を見て、容量wまで使えるときの最大価値
品物を1つずつ見ながら、「この品物を入れない場合」と「この品物を入れる場合」を比べます。
DPの更新ルール
品物 i の重さを weights[i - 1]、価値を values[i - 1] とすると、次のように更新できます。
dp[i][w] = dp[i - 1][w];これは「品物 i を入れない」場合です。前の行の答えをそのまま使います。
if (w >= weights[i - 1]) {
int candidate = dp[i - 1][w - weights[i - 1]] + values[i - 1];
if (candidate > dp[i][w]) {
dp[i][w] = candidate;
}
}これは「品物 i を入れる」場合です。入れられる重さが残っているなら、入れたときの価値を計算し、より大きいほうを採用します。
DP版の完成コード
C言語では2次元配列のサイズをコンパイル時に決める書き方もできますが、ここでは n と capacity に合わせて配列を作れるように、C99以降の可変長配列（VLA）を使います。
#include <stdio.h>
int max(int a, int b) {
return a > b ? a : b;
}
int knapsack_dp(int weights[], int values[], int n, int capacity) {
int dp[n + 1][capacity + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
dp[i][w] = 0;
}
}
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
dp[i][w] = dp[i - 1][w];
if (w >= weights[i - 1]) {
int candidate = dp[i - 1][w - weights[i - 1]] + values[i - 1];
dp[i][w] = max(dp[i][w], candidate);
}
}
}
return dp[n][capacity];
}
int main(void) {
int weights[] = {2, 1, 3, 2};
int values[] = {3, 2, 4, 2};
int n = 4;
int capacity = 5;
int answer = knapsack_dp(weights, values, n, capacity);
printf("最大価値: %d\n", answer);
return 0;
}実行結果は、全探索と同じく 7 です。
gcc -std=c99 knapsack_dp.c -o knapsack_dp
./knapsack_dp最大価値: 7その3：1次元DPでメモリを節約する
さきほどのDPは、dp[n + 1][capacity + 1] という2次元配列を使いました。考え方はわかりやすいのですが、容量が大きくなるとメモリをたくさん使います。
実は、0/1ナップサック問題では dp[w] だけを持つ1次元DPにもできます。
for (int i = 0; i < n; i++) {
for (int w = capacity; w >= weights[i]; w--) {
dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
}
}ここで大事なのは、w を大きいほうから小さいほうへ動かすことです。
小さいほうから更新してしまうと、同じ品物を同じ回の中で何度も使ったような状態になります。0/1ナップサックでは各品物は1回だけなので、後ろから更新します。
1次元DP版の完成コード
#include <stdio.h>
int max(int a, int b) {
return a > b ? a : b;
}
int knapsack_dp_1d(int weights[], int values[], int n, int capacity) {
int dp[capacity + 1];
for (int w = 0; w <= capacity; w++) {
dp[w] = 0;
}
for (int i = 0; i < n; i++) {
for (int w = capacity; w >= weights[i]; w--) {
dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}
int main(void) {
int weights[] = {2, 1, 3, 2};
int values[] = {3, 2, 4, 2};
int n = 4;
int capacity = 5;
int answer = knapsack_dp_1d(weights, values, n, capacity);
printf("最大価値: %d\n", answer);
return 0;
}こちらも答えは 7 です。
gcc -std=c99 knapsack_dp_1d.c -o knapsack_dp_1d
./knapsack_dp_1d最大価値: 7全探索とDPの違い
最後に、全探索とDPの違いを整理しておきます。
| 方法 | 考え方 | 計算量の目安 | 特徴 |
|---|---|---|---|
| 全探索 | すべての選び方を試す | O(n * 2^n) | わかりやすいが品物が増えると重い |
| 2次元DP | 品物数と容量で表を作る | O(n * capacity) | 理解しやすく、途中の状態も見やすい |
| 1次元DP | 容量だけの配列で更新する | O(n * capacity) | メモリを節約できる |
DPは、容量 capacity が大きすぎる場合には注意が必要ですが、全探索よりずっと現実的に使える場面が多いです。
C言語で書くときの注意点
- 配列の要素数は自動では渡らないので、
nを一緒に渡す 1 << nを使う全探索は、nが大きいとオーバーフローにも注意する- 2次元DPの配列は大きくなりやすいので、容量が大きいときは1次元DPも検討する
- この記事のDPコードはC99以降の可変長配列を使っているため、コンパイル時に
-std=c99を付けるとわかりやすい
まとめ
ナップサック問題は、アルゴリズムの考え方がぎゅっと詰まった定番問題です。
- 全探索では、すべての選び方をビットで表して試せる
- 品物が増えると、全探索は急に重くなる
- DPを使うと、同じような計算を表に保存して効率よく解ける
- C言語では配列サイズやメモリ使用量を意識すると理解が深まる
最初は全探索で「全部試す」感覚をつかみ、そのあとDPで「前に計算した答えを使い回す」感覚に進むと、ナップサック問題はかなり理解しやすくなります。
Pythonで学ぶナップサック問題
Pythonでリストを使って解きたい場合は、こちらの記事も参考にしてください。
C言語の次にUnityやUnreal Engineを学ぶ選択肢
用途ごとに選ぶ C言語のおすすめ本
