2014 Data Structures and Algorithms



  1. このコードを参考にしつつ、307~309ページのコイン問題を解くコードを書いてみよう。
    • 今回だけは,他の人と相談してはダメです。分かった人は,他の人に教えてはダメです。
    • コードを変更したすべての箇所について,理由を説明してもらいます。
  2. (2015/1/7追加の発展課題) どの品物を何個選べばよいかも表示させるようにしてみよう。(ヒント:どの品物を何個選んでいるかを表す配列を用意する。)
#include <stdio.h>
#include <stdlib.h>
 
/* 商品の数と,それぞれの大きさ,価値 */
#define N 5
int size[N] = {2, 3, 5, 6, 9};
int value[N] = {2, 4, 7, 10, 14};
 
/* ナップザックの大きさ */
#define NAP_SIZE 16
 
int main(void) {
    /* ナップザックの現時点での価値 */
    int nap_value[NAP_SIZE + 1] = {0};
    int i, j, new_value;
 
    printf("ナップザックの大きさ:");
    for(i = 1; i < NAP_SIZE + 1; i++) {
        printf("%2d ", i);
    }
    printf("\n\n");
 
    /* 扱う品物を,1つずつ増やしていく */
    for(i = 0; i < N; i++) {
        /* ナップザックの大きさがjのものに対して,
           品物i番を入れてみる */
        for(j = size[i]; j < NAP_SIZE + 1; j++) {
            /* 品物iを入れてみた場合,新しい価値はどう変わるか */
            new_value = nap_value[j - size[i]] + value[i];
 
            if(new_value > nap_value[j]) {
                nap_value[j] = new_value;
            }
        }
 
        printf("     品物 %dまで使う:", i + 1);
        for(j = 1; j < NAP_SIZE + 1; j++) {
            printf("%2d ", nap_value[j]);
        }
        printf("\n");
    }
 
    return EXIT_SUCCESS;
}



コードを次のように変更してみよう。
  1. 配列valueの値をランダムに決めて、問題を解かせてみよう。
#include <stdio.h>
#include <stdlib.h>
 
/* 与えられた値と,その分割方法 */
#define N 10
#define SEPARATOR 3
int value[N] = {15, 3, 7, 6, 10, 4, 13, 2, 3, 6};
int sep_pos[SEPARATOR] = {0};
 
/* 最適な分割と,そのなかのグループの最大和 */
int best_sep_pos[SEPARATOR] = {0};
int best_sep_max_value = 9999;
 
/* 分割を実装する再帰関数 */
void separate(int pos, int num) {
    int i, j, k, start, end, max;
 
    /* 新しい分割場所を設定 */
    sep_pos[num++] = pos;
 
    /* 分割がすべて決まったら */
    if(num == SEPARATOR) {
        max = 0;
 
        /* 設定された分割で,最大のグループ和を算出する */
        for(i = 0; i <= SEPARATOR; i++) {
            start = (i == 0)? 0: sep_pos[i-1];
            end = (i == SEPARATOR)? N: sep_pos[i];
            k = 0;
            for(j = start; j < end; j++) {
                k+=value[j];
            }
            if(k > max) {
                max = k;
            }
        }
 
        /* 最大のグループ和が保存されている和より小さければ */
        if(max < best_sep_max_value) {
            /* 現在の分割を保存する */
            best_sep_max_value = max;
            for(i = 0; i < SEPARATOR; i++) {
                best_sep_pos[i] = sep_pos[i];
            }
        }
        return;
    }
 
    /* 次の分割場所を設定する */
    for(i = pos + 1; i < N - SEPARATOR + num + 1; i++) {
        separate(i, num);
    }
}
 
int main(void) {
    int i, j, start, end;
 
    /* 最初の分割場所を設定して再帰を呼び出す */
    for(i = 0; i < N - SEPARATOR + 1; i++) {
        separate(i,0);
    }
 
    /* 保存された分割場所を表示する */
    for(i = 0; i <= SEPARATOR; i++) {
        start = (i == 0)? 0: best_sep_pos[i - 1];
        end = (i == SEPARATOR)? N: best_sep_pos[i];
        for(j = start; j < end; j++) {
            printf("%d ", value[j]);
        }
        if(end != N) {
            printf("|");
        }
    }
 
    return EXIT_SUCCESS;
}



コードについて次のことを調べてみよう。
  1. 配列arrayの値をランダムに決めて、問題を解かせてみよう。
  2. list11-2.cと実行時間を比較してみよう。
#include <stdio.h>
#include <stdlib.h>
 
// 個数
#define N 10
// セパレートの数
#define SEPARATOR 3
 
// 与えられる配列
const int array[N]={15, 3, 7, 6, 10, 4, 13, 2, 3, 6};
 
#define MAX(a, b) (((a) > (b))? (a): (b))
 
// 表のセルに当たる構造体
typedef struct {
    // この地点の最適の解
    int     sol;
    // その地点から何個か
    int     num;
} cell;
 
int main(void) {
    cell solutions[N][SEPARATOR + 1];
    int i, j, s, sum;
 
    // 表の後ろの方から順に埋めていく
    for(i = N - 1; i >= 0; i--) {
        for(j = 0; j < SEPARATOR + 1; j++) {
            solutions[i][j].num = 0;
            for(sum = 0, s = i; s < N; s++) {
                sum += array[s];
                if(j == 0 || i == N - 1 || solutions[i][j].num == 0
                    || (s != N - 1 && solutions[i][j].sol
                            > MAX(sum, solutions[s + 1][j - 1].sol))) {
                    if(j == 0 || i == N - 1) {
                        // 1行目かもしくは最終列ならば,処理なし
                        solutions[i][j].sol = sum;
                    } else {
                        // よりよい解決方法を記録する
                        solutions[i][j].sol =
                                MAX(sum, solutions[s + 1][j - 1].sol);
                    }
                    solutions[i][j].num = s - i + 1;
                }
            }
        }
    }
 
    // デバッグ用にテーブルを表示
    for(j = 0; j < SEPARATOR + 1; j++) {
        for(i = 0; i < N; i++) {
            printf("%2d,%2d "
                    , solutions[i][j].num, solutions[i][j].sol);
        }
        printf("\n");
    }
 
    printf("\n最大の和:%d\n分割方法:"
                    , solutions[0][SEPARATOR].sol);
    for(i = 0, j = SEPARATOR; j >=0 && i != N; j--) {
        printf("[%d個] ", solutions[i][j].num);
        i += solutions[i][j].num;
    }
 
    return 0;
}