ナップサック問題を動的計画法で解く完全ガイド

アルゴリズムの定番問題を視覚的に理解し、実際のコード実装まで学習。効率的な動的計画法の考え方をマスターできます。

プログラマーなら一度は挫折する「ナップサック問題」

こんな悩みありませんか？

• 動的計画法の概念は理解できるが、実装で手が止まってしまう
• ナップサック問題の解き方がいまいち理解できない
• アルゴリズムの勉強で挫折している
• 面接対策でDP問題を克服したい

神奈川でWeb制作を20年以上手がけてきた弊社でも、新人エンジニアがアルゴリズム学習で最初につまずくのがこのナップサック問題です。特に動的計画法（Dynamic Programming: DP）の考え方は、一度理解すれば応用範囲が広く、システム開発における最適化問題の解決に大いに役立ちます。

実際に、弊社のあるクライアントでは、ECサイトの在庫配分最適化にナップサック問題のアプローチを応用し、在庫回転率を35%改善した実績があります。アルゴリズムは単なる学習課題ではなく、実務で活用できる強力な武器なのです。

なぜナップサック問題は理解しにくいのか

多くのエンジニアがナップサック問題で挫折する理由は、状態遷移の可視化ができていないことにあります。テキストベースの説明だけでは、DPテーブルの各セルがどのような意味を持ち、どのように値が更新されていくのかが直感的に理解できません。

また、従来の教材では以下の問題があります：

• 数式中心の説明で実装イメージが湧かない
• 小さすぎる例題で実用性が感じられない
• デバッグ方法や最適解の復元方法が不明
• 計算量の改善手法が説明されていない

弊社の開発チームでも、当初はベテランエンジニアでさえDPの実装で時間を要していました。しかし、視覚的な理解方法を確立してからは、新人でも2-3日でマスターできるようになりました。

視覚的理解から始めるナップサック問題

問題設定の可視化

まず、具体的な例で問題を理解しましょう。容量10kgのナップサックに、以下の品物から最大価値になるように選んで入れる問題を考えます。

DPテーブルの構築プロセス

動的計画法では、dp[i][w]を「i番目までの品物を使って、重量制限wの場合の最大価値」として定義します。重要なのは、この定義を常に意識することです。

<?php
function knapsack($items, $capacity) {
    $n = count($items);
    // DPテーブルの初期化
    $dp = array_fill(0, $n + 1, array_fill(0, $capacity + 1, 0));
    
    for ($i = 1; $i <= $n; $i++) {
        $weight = $items[$i-1]['weight'];
        $value = $items[$i-1]['value'];
        
        for ($w = 0; $w <= $capacity; $w++) {
            // 品物iを選ばない場合
            $dp[$i][$w] = $dp[$i-1][$w];
            
            // 品物iを選ぶ場合（重量制限内なら）
            if ($weight <= $w) {
                $with_item = $dp[$i-1][$w - $weight] + $value;
                $dp[$i][$w] = max($dp[$i][$w], $with_item);
            }
        }
    }
    
    return ['max_value' => $dp[$n][$capacity], 'dp_table' => $dp];
}

// 使用例
$items = [
    ['weight' => 1, 'value' => 60],  // 宝石
    ['weight' => 4, 'value' => 100], // 時計
    ['weight' => 3, 'value' => 20],  // 書籍
    ['weight' => 5, 'value' => 80],  // カメラ
    ['weight' => 6, 'value' => 120]  // ノートPC
];

$result = knapsack($items, 10);
echo "最大価値: " . $result['max_value'] . "\n";
?>

function knapsack(items, capacity) {
    const n = items.length;
    // DPテーブルの初期化
    const dp = Array(n + 1).fill().map(() => Array(capacity + 1).fill(0));
    
    for (let i = 1; i <= n; i++) {
        const {weight, value} = items[i-1];
        
        for (let w = 0; w <= capacity; w++) {
            // 品物iを選ばない場合
            dp[i][w] = dp[i-1][w];
            
            // 品物iを選ぶ場合（重量制限内なら）
            if (weight <= w) {
                const withItem = dp[i-1][w - weight] + value;
                dp[i][w] = Math.max(dp[i][w], withItem);
            }
        }
    }
    
    return {maxValue: dp[n][capacity], dpTable: dp};
}

// 使用例
const items = [
    {weight: 1, value: 60},  // 宝石
    {weight: 4, value: 100}, // 時計
    {weight: 3, value: 20},  // 書籍
    {weight: 5, value: 80},  // カメラ
    {weight: 6, value: 120}  // ノートPC
];

const result = knapsack(items, 10);
console.log('最大価値:', result.maxValue);

最適解の復元

最大価値を求めるだけでなく、どの品物を選んだかを知る必要がある場合は、DPテーブルを逆算して最適解を復元します。

function getOptimalItems($items, $dp, $capacity) {
    $n = count($items);
    $selected = [];
    $w = $capacity;
    
    for ($i = $n; $i > 0; $i--) {
        // 値が変わっていれば、その品物を選んだ
        if ($dp[$i][$w] != $dp[$i-1][$w]) {
            $selected[] = $i - 1; // 0ベースのインデックス
            $w -= $items[$i-1]['weight'];
        }
    }
    
    return array_reverse($selected);
}

空間計算量の最適化

上記の実装では、O(n × capacity)の空間が必要です。しかし、前の行の情報しか使わないため、1次元配列で実装できます。

function knapsackOptimized($items, $capacity) {
    $dp = array_fill(0, $capacity + 1, 0);
    
    foreach ($items as $item) {
        $weight = $item['weight'];
        $value = $item['value'];
        
        // 逆順でループすることで上書きを防ぐ
        for ($w = $capacity; $w >= $weight; $w--) {
            $dp[$w] = max($dp[$w], $dp[$w - $weight] + $value);
        }
    }
    
    return $dp[$capacity];
}

この最適化により、空間計算量をO(capacity)に削減できます。

よくある失敗パターンと対処法

失敗パターン1: ループの順番ミス

1次元配列での最適化実装で、重量のループを昇順で回してしまうケースです。

// ❌ 間違った実装
for ($w = $weight; $w <= $capacity; $w++) {
    $dp[$w] = max($dp[$w], $dp[$w - $weight] + $value);
}

// ✅ 正しい実装
for ($w = $capacity; $w >= $weight; $w--) {
    $dp[$w] = max($dp[$w], $dp[$w - $weight] + $value);
}

昇順でループすると、同じ品物を複数回選んでしまう「無限ナップサック問題」になってしまいます。

失敗パターン2: 配列の初期化忘れ

// ❌ 初期化を忘れがち
$dp = [];

// ✅ 適切な初期化
$dp = array_fill(0, $capacity + 1, 0);

弊社でも新人エンジニアがよくこの初期化でエラーを起こしていました。特にPHPでは配列の型が柔軟な分、意図しない動作になりやすいので注意が必要です。

失敗パターン3: 境界値の処理ミス

// ❌ 境界値チェック漏れ
if ($weight < $w) { // 等号漏れ
    // 処理
}

// ✅ 正しい境界値チェック
if ($weight <= $w) {
    // 処理
}

失敗パターン4: デバッグ情報の不足

動的計画法の問題では、中間状態の確認が重要です。デバッグ用の関数を用意しておくと効率的です。

function debugDP($dp, $items) {
    echo "DPテーブル:\n";
    echo "重量\t";
    for ($w = 0; $w < count($dp[0]); $w++) {
        echo $w . "\t";
    }
    echo "\n";
    
    for ($i = 0; $i < count($dp); $i++) {
        if ($i == 0) {
            echo "初期\t";
        } else {
            echo $items[$i-1]['weight'] . "kg\t";
        }
        for ($w = 0; $w < count($dp[$i]); $w++) {
            echo $dp[$i][$w] . "\t";
        }
        echo "\n";
    }
}

実務での応用例

弊社では、以下のような場面でナップサック問題の考え方を活用しています：

ECサイトの在庫配分最適化

class InventoryOptimizer {
    public function optimizeAllocation($products, $budget) {
        // 各商品を「価値=予想利益、重量=仕入れコスト」として扱う
        $items = [];
        foreach ($products as $product) {
            $items[] = [
                'weight' => $product['cost'],
                'value' => $product['expected_profit'],
                'id' => $product['id']
            ];
        }
        
        return $this->knapsack($items, $budget);
    }
}

この最適化により、あるクライアントでは仕入れ効率が35%向上し、在庫回転率も大幅に改善されました。

リソース配分の最適化

サーバーリソースの配分や、開発チームのタスク割り当てでも応用できます。

まとめと次のステップ

ナップサック問題の動的計画法による解法は、以下のポイントを押さえれば確実にマスターできます：

1. 状態の定義を明確にする: dp[i][w]が何を表すかを常に意識
2. 漸化式を丁寧に実装: 「選ぶ・選ばない」の分岐を正確に
3. 境界値の処理: 配列の初期化と範囲チェック
4. 最適化は段階的に: まず動く実装を作ってから改良

弊社では、新人エンジニアにはまずこの問題をマスターしてもらい、その後より複雑な最適化問題に取り組んでもらっています。実際の業務でも、在庫管理やリソース配分など様々な場面で活用できる実用的なスキルです。

アルゴリズムは一見学術的に見えますが、実は日常の開発業務で直面する問題解決に直結します。ぜひこの機会に動的計画法をマスターし、より効率的な開発者としてのスキルを身につけてください。