授業中に示した、ナップサック問題を最長経路問題に変換するアルゴリズムについて、
最長経路問題に相応しいグラフ情報を出力するプログラムを作成せよ。
グラフの定義として必要十分な情報が示されていれば、テキスト表現でよい（図示する必要は無い）。
実行結果を示す場合は、下記の制約条件下で行うこと。
#define W_LIMIT 112
#define N 8 // 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}
}; |
|
【注意】 | |
| 誰かに教えてもらった場合： | 教えてくれた学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） |
| 誰かに教えてあげた場合： | その学生（氏名・学籍番号）をプログラム先頭に記すこと。 |
| お互いに相談した場合： | 教えてもらった・教えてあげたの例に準拠して提出してください。 |
任意の指定金額の支払いにおける硬貨枚数最小化問題について、greedy algorithmで最適解が得られる硬貨の組み合わせを以下の中から全て選び、その理由を述べよ。
(10,5,1) (10,7,3) (6,3,2) (9,6,1)
(10,8,1) ( 6,4,1) (6,3,1) (9,3,1)
以前の授業で説明した最長経路問題を解くアルゴリズムをもとに、C言語プログラムを作成し、課題５Ａを実際に解いてみせよ。
ナップサック問題の具体例としては、課題５Ａに提示したものを使うこと。
|
【注意】 | |
| 誰かに教えてもらった場合： | 教えてくれた学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） |
| 誰かに教えてあげた場合： | その学生（氏名・学籍番号）をプログラム先頭に記すこと。 |
| お互いに相談した場合： | 教えてもらった・教えてあげたの例に準拠して提出してください。 |