＝＝＝課題８＝＝＝

受付開始日時
2015-06-16 11:30
受付終了日時
2015-06-22 18:00
閲覧設定	提出者本人と教員のみ閲覧・コメント可（個別指導）
学生による再提出の許可 	再提出を許可する

●必須課題8-1 [プログラム(zip)] 重複を許すKnapsack問題を解く動的計画法プログラム
課題に関する説明
・授業で示した動的計画法に基づくKnapsack問題を解くプログラムについて，下記の仕様を満たすよう修正して完成させなさい．
・最適解（合計価値の最大）と，そのときの合計重量，それを実現する品物の組み合わせを標準出力に出すこと．
・物体を増やして処理を進めていくところで，途中経過をわかりやすく標準出力に示すこと．
・中心的な処理を行う２重ループ中のif文の評価回数をカウントして，実行中に表示すること．
・具体的な問題（品物の価値と重量）として下記を設定すること．
〜〜〜
#define WLIMIT 114
struct {
	
  int v; // value
  int w; // weight

} obj[N] = {

  { 15,  7},

  {  2,  3},

  { 90, 25},

  { 60, 30},

  { 40, 40},

  { 25, 30},

  { 10, 60},

  { 13, 10}
};
〜〜〜

・プログラムソースの先頭に，学生番号，氏名，課題名をコメントで記入すること．
・プログラムで工夫した部分について、プログラムソースの何行目付近を確認してほしいか明記し（複数場所可）、其々の場所では何かしらの説明をコメントの形でプログラム中に書き込むこと．
・実行結果は，Result.txtに保存すること．
・解答開始から解答終了までの処理時間をミリ秒の単位でプログラム内で計測し表示すること（昨年度のプログラミング序論３を参考にせよ）
・Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。

⇒誰かに教えてもらった場合：その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を独自の説明で数行以上書き込むこと。 （教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。）
⇒誰かに教えてあげた場合：その学生（氏名・学籍番号）をプログラム先頭に記すこと。
⇒お互いに相談した場合：お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。

●必須課題8-2 [記述(pdf)] 問題の置換
課題に関する説明
・ナップサック問題を解く際に，まずナップサック問題を最長経路問題に書き換え，そのあとで最長経路問題を実行することを考える．
(1) 頂点数Nのグラフに対する最長経路問題を解くアルゴリズムを簡潔に示しなさい．((1)の議論をするのに必要な程度には示すこと)
(2) 頂点数Nのグラフに対する最長経路問題の空間計算量と時間計算量を議論しなさい．
(3) K個の物体，重量制限L(正整数)に対するナップサック問題をグラフに書き換える方法を示しなさい．
(4) (3)にかかる空間計算量と時間計算量を議論しなさい．
(5) 問題の置換から最長経路問題の実施まで，全体としてかかる空間計算量と時間計算量を議論しなさい．
・先頭に学籍番号・氏名・課題番号を示すこと．


◇発展課題8-A [プログラム(zip)] 問題の置換を実行するプログラム
課題に関する説明
・課題8-2(3)で示したアルゴリズムをＣ言語で実装しなさい．
・結果は隣接行列の形で出力すること．
・隣接行列の各要素において，重みがある場合は正整数，ない場合は0とすること．
・物品のセットは課題8-1に示したものを使うこと．
・実行結果は Result.txt に保存して提出すること．
・プログラムソースの先頭に、学生番号、氏名、課題名をコメントで記入すること。
・プログラムで工夫した部分について、プログラムソースの何行目付近を確認してほしいか明記し（複数場所可）、其々の場所では何かしらの説明をコメントの形でプログラム中に書き込むこと。
・Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。

⇒誰かに教えてもらった場合：その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を独自の説明で数行以上書き込むこと。 （教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。）
⇒誰かに教えてあげた場合：その学生（氏名・学籍番号）をプログラム先頭に記すこと。
⇒お互いに相談した場合：お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。

◇発展課題8-B [プログラム(zip)] 問題の置換を実行するプログラム
課題に関する説明
(1) 課題4-Aで作成したプログラムで，課題8-Aで出力した隣接行列を処理しなさい．
・実行結果は標準出力をの形で出力し，それをResult-R.txtに保存すること．
・計算コストを示せればなおよい．
(2) 課題8-Aで作成したプログラムで，課題8-1に示した物品セットと重量制限に対する解を得なさい．
・実行結果は標準出力をの形で出力し，それをResult-K.txtに保存すること．
・計算コストを示せればなおよい．
(3) 二つの結果を比較し，議論しなさい．
・解の見かたについても説明すること．
・計算コストについて，課題8-Aとの整合性について議論すること．
・プログラムソースの先頭に、学生番号、氏名、課題名をコメントで記入すること。
・プログラムで工夫した部分について、プログラムソースの何行目付近を確認してほしいか明記し（複数場所可）、其々の場所では何かしらの説明をコメントの形でプログラム中に書き込むこと。
・Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。