C言語で学ぶ0-1ナップサック問題：動的計画法による解法と実装例

0-1ナップサック問題とは

ナップサック（knapsack）とは、背負い袋のことです。ナップサック問題は、価値と重さがそれぞれ異なる複数のアイテムの中から、容量に制限のある袋へ入れる品物を選び出し、袋の中の価値の合計を最大化することを目指す古典的な最適化問題です。

特に「0-1ナップサック問題」では、各アイテムについて「入れる（1）」か「入れない（0）」かのどちらかしか選べません。アイテムを分割して一部だけ入れるという概念は存在しない点が大きな特徴です。

例題

アイテムの価値 = {20, 25, 40}
アイテムの重さ = {25, 20, 30}
ナップサックの容量 = 50

重さの組み合わせの検証

{1, 2}：重さ = 25 + 20 = 45、価値 = 20 + 25 = 45
{2, 3}：重さ = 20 + 30 = 50、価値 = 25 + 40 = 65

もし {1, 3} の組み合わせを選ぶと、重さが 55 となり最大許容値の 50 を超えてしまうため、この選択は不可能です。

上記の比較から、価値の合計が最大となるのは 65 の場合であることが分かります。したがって、アイテム2とアイテム3をナップサックに入れるのが最適解となります。

アルゴリズムの考え方（動的計画法）

この問題は動的計画法（DP）を用いて効率的に解けます。2次元の表 knap[i][w] を用意し、「i番目までのアイテムの中から、容量 w 以内で選んだときに得られる最大価値」を順に埋めていきます。

• i が 0 または w が 0 のとき：価値は 0
• アイテム i の重さが容量 w 以下の場合：「そのアイテムを入れた場合」と「入れなかった場合」の価値の大きい方を採用
• それ以外の場合：前の状態 knap[i-1][w] をそのまま引き継ぐ

計算量は O(nW)、必要なメモリ量も O(nW) で抑えられます。

0-1ナップサック問題を解くC言語プログラム

#include<stdio.h>
int max(int a, int b) {
    if(a>b){
        return a;
    } else {
        return b;
    }
}
int knapsack(int W, int wt[], int val[], int n) {
    int i, w;
    int knap[n+1][W+1];
    for (i = 0; i <= n; i++) {
        for (w = 0; w <= W; w++) {
            if (i==0 || w==0)
                knap[i][w] = 0;
            else if (wt[i-1] <= w)
                knap[i][w] = max(val[i-1] + knap[i-1][w-wt[i-1]], knap[i-1][w]);
            else
                knap[i][w] = knap[i-1][w];
        }
    }
    return knap[n][W];
}
int main() {
    int val[] = {20, 25, 40};
    int wt[] = {25, 20, 30};
    int W = 50;
    int n = sizeof(val)/sizeof(val[0]);
    printf("The solution is : %d", knapsack(W, wt, val, n));
    return 0;
}

実行結果

The solution is : 65

プログラムを実行すると、期待通り最大価値の「65」が出力されます。これは先ほど手作業で確認した結果と一致しており、動的計画法による実装が正しく機能していることを示しています。