跳到主要内容

名古屋大学 情報科学研究科 情報システム学専攻 2012年8月実施 プログラミング

标签：

Author​

祭音Myyura (co-authored with GPT 6 Astra)

Description​

それぞれの重量と価格が分かっている NN 個の商品から、総重量が定められた上限値 limit 以下となるように任意個選択したときの合計価格のうちで、最大値を計算したい。リスト 1 は、この計算をするための C 言語プログラムである。構造体 item は商品を表し、そのメンバ w、p はそれぞれ重量と価格を表す。NN 個の商品は配列 items に格納されている。maxtotal(num, start) を呼び出すことにより、総重量に start を加えた重量が limit 以下であるという条件のもとで、インデックスが num 以降の商品から任意個選択したときの合計価格の最大値が得られる。リスト 1 の左側の番号は行番号であり、プログラムの一部ではない。このプログラムについて、以下の問いに答えよ。

(1) リスト 1 の (a) から (e) を埋めてプログラムを完成せよ。

(2) リスト 1 の 33 行目が実行された際に 10 を入力した場合、関数 maxtotal が呼び出される回数をその理由とともに答えよ。

(3) リスト 1 の 33 行目が実行された際に 2 を入力した場合、関数 maxtotal が呼び出される回数を理由とともに答えよ。

次に、リスト 1 のプログラムの高速化を考える。プログラムの高速化を目的とした最適化技法の一つとしてメモ化がある。メモ化は、プログラム中の関数呼び出しの結果を呼び出し時の引数とともに記憶しておき、同じ引数で呼び出された際に再度計算せずに、記憶している値を利用する方法である。リスト 2 は、配列 memo を用いてリスト 1 の関数 maxtotal にメモ化を適用したものである。以下の問いに答えよ。

(4) リスト 2 の (f) から (i) を埋めてプログラムを完成せよ。(a) から (e) は (1) で埋めたものと同一である。

(5) リスト 2 の 48 行目が実行された際に 20 を入力したとき、maxtotal(4, 3) が呼び出される回数が、リスト 2 の 25 行目を行数を変化させずにコメントアウトした場合と比べて何回削減されるかを理由とともに答えよ。

(6) 関数の性質によっては、メモ化は適用できない場合がある。そのような場合を 2 つ挙げて説明せよ。

専門用語​

日本語English
関数function
引数argument
構造体structured type
メンバmember
配列array
最適化技法optimization technique
メモ化memoization
コメントアウトcomment out

リスト 1​

#include <stdio.h>

#define N 4

typedef struct _item {
    int w;
    int p;
} item;

int limit;
item items[N] = {
    {1, 100}, {1, 50}, {2, 150}, {2, 100}
};

int maxtotal(int num, int start) {
    int x, y, rval;
    if (num == N) {
        return 0;
    }

    if ( [ (a) ] > limit ) {
        rval = maxtotal( [ (b) ], [ (c) ] );
    } else {
        x = maxtotal(num + 1, [ (d) ]) + items[num].p;
        y = maxtotal(num + 1, [ (e) ]);
        rval = x > y ? x : y;
    }
    return rval;
}

int main(void) {
    printf("\nWeight limit?:");
    scanf("%d", &limit);
    printf("Maximum total price is %d\n", maxtotal(0, 0));
    return 0;
}

リスト 2​

#include <stdio.h>

#define N 6
#define TOTAL_W 15

typedef struct _item {
    int w;
    int p;
} item;

int limit;
item items[N] = {
    {1, 100}, {2, 150}, {1, 50}, {2, 100}, {4, 200}, {5, 250}
};
int memo[N][TOTAL_W];

int maxtotal(int num, int start) {
    int x, y, rval;

    if (num == N) {
        return 0;
    }

    if (memo[num][start] > -1) {
        return [ (f) ];
    }

    if ( [ (a) ] > limit ) {
        rval = maxtotal( [ (b) ], [ (c) ] );
    } else {
        x = maxtotal(num + 1, [ (d) ]) + items[num].p;
        y = maxtotal(num + 1, [ (e) ]);
        rval = x > y ? x : y;
    }
    memo[ [ (g) ] ][ [ (h) ] ] = [ (i) ];
    return rval;
}

int main(void) {
    int i, j;
    for (i = 0; i < N; i++) {
        for (j = 0; j < TOTAL_W; j++) {
            memo[i][j] = -1;
        }
    }

    printf("\nWeight limit?:");
    scanf("%d", &limit);
    printf("Maximum total price is %d\n", maxtotal(0, 0));
    return 0;
}

题目描述​

已知 NN 件商品各自的重量和价格。任意选择若干件，使总重量不超过给定上限 limit，求所选商品总价格的最大值。程序清单 1 是用于完成这一计算的 C 程序。结构体 item 表示商品，成员 w 和 p 分别表示重量与价格。NN 件商品存储在数组 items 中。调用 maxtotal(num, start)，可以求出从下标不小于 num 的商品中任意选择若干件时，在“所选商品总重量加上 start 不超过 limit”这一条件下的最大总价格。程序清单 1 左侧的数字是行号，不是程序的一部分。请回答以下问题。

(1) 填写程序清单 1 中的空格 (a) 至 (e)，使程序完整。

(2) 在执行程序清单 1 的第 33 行时输入 10，函数 maxtotal 会被调用多少次？说明理由。

(3) 在执行程序清单 1 的第 33 行时输入 2，函数 maxtotal 会被调用多少次？说明理由。

接下来考虑加快程序清单 1 的运行速度。记忆化是以提高程序运行速度为目的的一种优化技术：将函数调用的结果与调用时的参数一起保存，再次以相同参数调用时，直接使用保存的值，不重新计算。程序清单 2 使用数组 memo，对程序清单 1 中的函数 maxtotal 进行了记忆化。请回答以下问题。

(4) 填写程序清单 2 中的空格 (f) 至 (i)，使程序完整。(a) 至 (e) 与第 (1) 问填写的内容相同。

(5) 在执行程序清单 2 的第 48 行时输入 20。与将该程序第 25 行注释掉、但不改变行数的情况相比，maxtotal(4, 3) 的调用次数减少了多少次？说明理由。

(6) 某些函数由于自身的性质，不能应用记忆化。请举出两种这样的情形并说明。

两份程序清单完整见上文，代码、空格与行号保持相同含义。术语对应为：関数＝函数，引数＝参数，構造体＝结构体，メンバ＝成员，配列＝数组，最適化技法＝优化技术，メモ化＝记忆化，コメントアウト＝注释掉。

Kai​

(1)​

空欄解答
(a)start + items[num].w
(b)num + 1
(c)start
(d)start + items[num].w
(e)start

start は既に選んだ商品の総重量である。商品 num を追加すると上限を超える場合は、その商品を選ばず次へ進む。追加できる場合は、選ぶ場合の最大価格 x と選ばない場合の最大価格 y を比較し、大きい方を返す。num == N では残りの商品がないため、追加できる価格は 0 である。

(2)​

31 回。 main からの最初の呼び出しと、num == N で直ちに戻る呼び出しも数える。

全商品の総重量は 1+1+2+2=6<101+1+2+2=6<10 なので、すべての非終端呼び出しが 2 個の再帰呼び出しを行う。したがって、num が 0,1,2,3,40,1,2,3,4 の各段階の呼び出し数はそれぞれ 1,2,4,8,161,2,4,8,16 であり、合計は

1+2+4+8+16=311+2+4+8+16=31

となる。

(3)​

18 回。 各段階における start の値と、その値で呼び出される回数を数える。

numstart = 0start = 1start = 2呼び出し数
01001
11102
21214
31225
41236

最初の 2 商品の重量はともに 1 であるため、num == 2 まではすべての選択・非選択の分岐が実行される。残る 2 商品の重量はともに 2 なので、各段階で start == 0 の呼び出しだけが 2 分岐し、それ以外は商品を選ばない 1 分岐となる。よって総数は

1+2+4+5+6=181+2+4+5+6=18

である。

(4)​

空欄解答
(f)memo[num][start]
(g)num
(h)start
(i)rval

memo[num][start] にその引数での計算結果を保存する。初期値 -1 は未計算を表す。何も選ばなければ価格は 0 なので、最大価格は非負であり、-1 と計算済みの値を区別できる。

(5)​

4 回から 2 回になり、2 回削減される。 キャッシュに保存された値を返すだけの場合も、関数の呼び出しとして数える。

総重量は 1+2+1+2+4+5=15<201+2+1+2+4+5=15<20 なので、重量制約によって分岐が減ることはない。25 行目をコメントアウトすると、保存値があっても再計算する。先頭 4 商品の重量は 1,2,1,21,2,1,2 であり、合計重量 3 となる選び方は、添字で表して

{0,1},{0,3},{1,2},{2,3}\{0,1\},\quad \{0,3\},\quad \{1,2\},\quad \{2,3\}

の 4 通りである。したがって、maxtotal(4, 3) は 4 回呼ばれる。

メモ化が有効な場合、maxtotal(4, 3) の直接の呼び出し元は次の 2 状態だけである。

呼び出し元商品 3 の扱い呼び出し
maxtotal(3, 1)重量 2 の商品を選ぶmaxtotal(4, 3)
maxtotal(3, 3)商品を選ばないmaxtotal(4, 3)

これらの呼び出し元は、それぞれ最初の 1 回だけ再帰部分を実行する。そのため maxtotal(4, 3) への呼び出しは合計 2 回であり、最初の呼び出しで計算して保存し、2 回目は保存値を返す。したがって、削減数は 4−2=24-2=2 回である。

(6)​

引数だけをキーとして戻り値を保存し、再呼び出し時に関数本体の実行を省略する方式では、例えば次の 2 つの場合にそのまま適用できない。

  1. 戻り値が引数だけでは決まらない場合。 現在時刻や乱数、変更される大域変数、外部入力などに依存する関数は、同じ引数でも異なる値を返し得る。以前の値を再利用すると、本来の戻り値と一致しない。
  2. 呼び出すたびに必要な副作用がある場合。 ファイルへの書き込み、画面への出力、大域変数の更新などを行う関数では、保存値を返すだけにすると、その呼び出しで必要な副作用が実行されず、プログラムの振る舞いが変わる。

本問の maxtotal も大域変数 limit と配列 items を参照するが、1 回の探索中はそれらが変化しないため、num と start をキーにできる。limit や items を変更して別の探索を行う場合には、キャッシュを初期化し直すなどの対応が必要である。

Reference​

本页目录