C言語

【C言語】第8章第11回：動的プログラミングの基礎

a-mun

動的プログラミング（Dynamic Programming）は、問題を分割して解くアルゴリズム設計手法です。本記事では、動的プログラミングの基礎から応用までを学びます。

0. 記事の概要

この記事を読むメリット

  • 問題解決力の向上：複雑な問題を効率的に解くための手法を習得します。
  • アルゴリズム設計の基礎理解：再帰とメモ化を使った効率化の考え方を学べます。
  • 実践的なスキル：C言語での動的プログラミングの実装方法を習得できます。

この記事で学べること

  • 動的プログラミングの基本概念と特性
  • メモ化とタブレーションの違い
  • 実際のプログラム例とその応用

活用のイメージ

動的プログラミングは、最短経路問題、配列の分割、組み合わせ最適化などの幅広い分野で利用されています。

1. 動的プログラミングの基本

1.1 動的プログラミングとは？

動的プログラミングは、問題を小さな部分問題に分割し、部分問題の解を再利用することで全体の効率を向上させる手法です。

1.2 動的プログラミングの特性

  • 最適部分構造：問題の最適解が部分問題の最適解で構成される
  • 部分問題の重複：同じ部分問題が繰り返し発生する

1.3 メモ化とタブレーション

  • メモ化：再帰的な解法にキャッシュを追加して効率化
  • タブレーション：ボトムアップアプローチでテーブルを埋める

2. 動的プログラミングの実装例

2.1 フィボナッチ数列の計算（メモ化）

#include <stdio.h>

#define MAX 100
int memo[MAX];

// フィボナッチ数列（メモ化）
int fib(int n) {
    if (n <= 1) {
        return n;
    }
    if (memo[n] != -1) {
        return memo[n];
    }
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main() {
    for (int i = 0; i < MAX; i++) {
        memo[i] = -1;
    }
    int n = 10;
    printf("Fibonacci(%d): %d\n", n, fib(n));
    return 0;
}
動作解説
  1. 初期化：メモ配列を-1で初期化し、計算済みの値がないことを示します。
  2. 再帰計算：既に計算済みの値があればそれを返し、計算していない場合は計算して保存します。
  3. 結果出力：指定したn番目のフィボナッチ数を出力します。

2.2 ナップサック問題（タブレーション）

#include <stdio.h>

#define MAX_ITEMS 100
#define MAX_WEIGHT 100

// ナップサック問題（タブレーション）
int knapsack(int weights[], int values[], int n, int W) {
    int dp[n + 1][W + 1];

    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;
            } else if (weights[i - 1] <= w) {
                dp[i][w] = (values[i - 1] + dp[i - 1][w - weights[i - 1]] > dp[i - 1][w])
                               ? values[i - 1] + dp[i - 1][w - weights[i - 1]]
                               : dp[i - 1][w];
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][W];
}

int main() {
    int weights[] = {1, 2, 3};
    int values[] = {6, 10, 12};
    int W = 5;
    int n = sizeof(weights) / sizeof(weights[0]);
    printf("Maximum value in Knapsack: %d\n", knapsack(weights, values, n, W));
    return 0;
}
動作解説
  1. 初期化：テーブルdpを0で初期化します。
  2. 再帰ケース：各アイテムを選ぶ場合と選ばない場合の値を比較します。
  3. 結果出力：最大値をテーブルの右下隅から取得して出力します。

3. 練習問題

以下の課題に挑戦して、動的プログラミングの理解を深めましょう。

  1. 再帰とメモ化を使用して最短経路問題を解くプログラムを作成してください。
  2. タブレーションを使用して部分和問題を解くプログラムを実装してください。
  3. カットロッド問題を動的プログラミングで解いてください。

4. 練習問題の解答と解説

問1の解答

// 最短経路問題（再帰とメモ化）
#include <stdio.h>

#define MAX 100
#define INF 1000000

int memo[MAX][MAX];

int min(int a, int b) {
    return a < b ? a : b;
}

int shortestPath(int grid[MAX][MAX], int m, int n) {
    if (m == 0 && n == 0) {
        return grid[m][n];
    }
    if (memo[m][n] != -1) {
        return memo[m][n];
    }

    int left = (n > 0) ? shortestPath(grid, m, n - 1) : INF;
    int up = (m > 0) ? shortestPath(grid, m - 1, n) : INF;

    memo[m][n] = grid[m][n] + min(left, up);
    return memo[m][n];
}

int main() {
    int grid[MAX][MAX] = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            memo[i][j] = -1;
        }
    }

    printf("Shortest Path: %d\n", shortestPath(grid, 2, 2));
    return 0;
}

このプログラムでは、再帰とメモ化を使用して最短経路を計算します。

5. まとめ

本記事では、動的プログラミングの基本概念と実装方法について学びました。次回は、さらに高度なアルゴリズムへの応用について掘り下げます。

こちらもおすすめ

【C言語】第10章第12回：センサー制御プログラムの開発

a-mun

【C言語】第2章第7回：break文とcontinue文の使い方

a-mun

【C言語】第6章第6回：列挙型の基本と使い方

a-mun