授業中に示した、重複を許すナップサック問題を動的計画法によって解くプログラムについて、
最大価値とその最大価値を達成する物品の組み合わせを表示するプログラムを作成せよ。
実行結果を示す場合は、下記の制約条件下で行うこと。
#define W_LIMIT 112
#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}
}; |
|
【注意】 | |
| 誰かに教えてもらった場合： | 教えてくれた学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） |
| 誰かに教えてあげた場合： | その学生（氏名・学籍番号）をプログラム先頭に記すこと。 |
| お互いに相談した場合： | 教えてもらった・教えてあげたの例に準拠して提出してください。 |
授業中に説明した、重複を許すナップサック問題をバックトラッキングで解くプログラムについて、時間計算量を考察せよ。
ただし、用意される物体の種類の数Ｎと、ナップサックの重量制約W_LIMITは、共に予め与えられるものとする一方で、
用意される物体種類のそれぞれの重量は１〜W_LIMITまでありえるとし、それぞれの価値は全て正値で与えられるものとする。
(ヒント：NとW_LIMITを用いたビッグオー表現を考えてみよ)
考察にはその根拠も示すこと。根拠が示されていない場合は正答でも得点はないものとする。
授業中に説明した、通常のナップサック問題をブランチ＆バウンドで解くプログラムについて、
実行終了時に最大価値とそれを実現する物品の組み合わせを表示するプログラムを作成せよ。
ナップサック問題の具体例としては、課題４Ａに提示したものを使うこと。
|
【注意】 | |
| 誰かに教えてもらった場合： | 教えてくれた学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） |
| 誰かに教えてあげた場合： | その学生（氏名・学籍番号）をプログラム先頭に記すこと。 |
| お互いに相談した場合： | 教えてもらった・教えてあげたの例に準拠して提出してください。 |