2013/06/18の授業中に説明した、重複を許すナップサック問題を解くアルゴリズム(6.3.3.B:動的計画法)をＣ言語で実装せよ。
(A)最適解（最大価値）を示すこと。
(B)最適解を与えるときの品種と個数を示すこと。
(C)最適解を与えるときの合計重量を示すこと。
提出プログラムは、下記の例題を設定した状態で提出すること。
// SAMPLE_K300
#define WEIGHT_LIMIT 113
#define N 8 // Number of object classes, Not number of objects
struct {
int v; // value
int w; // weight
} obj[N] = {
{ 15, 6},
{100, 20},
{ 90, 25},
{ 60, 30},
{ 40, 40},
{ 15, 30},
{ 10, 60},
{ 3, 10}
};
|
| 【状況】 | 【指示】 |
| 誰かに教えてもらった場合 | その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。
（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） |
| 誰かに教えてあげた場合 | その学生（氏名・学籍番号）をプログラム先頭に記すこと。 |
| お互いに相談した場合 | お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。 |
2013/6/18の授業中に再度説明したKnight-Tour問題の全解候補の数え上げ方式の２通り(便宜上ここではA/Bと呼ぶ)について、下記のことを示せ。
【立式】A/Bでの数え上げについて立式し、その内容を説明せよ。
【数値】A/Bの正確な解数を数値で示せ。その求め方も述べること。なお、正確な数値が求められない場合は、10のk乗という近似でもよい。その場合、近似までの導出を示せ。
【比較】A/Bどちらの解数のほうが多いか示せ。また、そうなった理由について（立式時の説明を引用しながら）考察せよ。
※立式まで解答があれば合格最低点は配する。
(2013/6/10, N=8を明記)
2013/06/11の授業で説明した、重複を許すナップサック問題を解くプログラム(6.3.3:ＤＰを用いない版 "No-DP")、2013/6/18の授業で説明したＤＰによるプログラム(6.3.3.A:ＤＰを用いる版 "DP-A"）、課題４Ａで作成したプログラム("DP-B")をmain()関数からそれぞれ呼び出して、計算コストを比較できるプログラムを作成せよ。
main()関数から上記アルゴリズム No-DP, DP-A, DP-B に従った別々の関数を３回呼び出す形で実行できること。
計算コストを計測するカウンタは、３つの関数内において比較時に妥当と思われる場所に設置し、その理由を該当部でコメントの形で説明せよ。
No-DP, DP-A, DP-Bのそれぞれについて、最適解とそれを求めるのに要したカウンタ数を表示すること。
提出プログラムでは例題として、課題4Aに示した SAMPLE_K300を使用すること。
No-DPの時間計算量を見積もってみせよ。
必要に応じて品種数Ｎ、重量制限ＷＬを用いてよい。また、必要と思えば他に妥当な値（変数）を導入してよい。
オーダー（ビッグオー）表現でよい。