ID非公開
ID非公開さん
2021/1/21 16:02
1回答
C言語で組み合わせの問題を学んでいます。
C言語で組み合わせの問題を学んでいます。 N個の入れ物があり、それぞれに入る量をaiとする。 (0<N<100, 0<a0<=a2<=...aN-1とする) 燃料Vが与えられたとき、量が満タンになっている入れ物の個数をなるべく多くしたい。なお、燃料は使い切らず残っても良い。 標準入力から個数、容量、燃料の量を入力すると満タンになる入れ物の個数を最大にするときに満タンにすべき入れ物の番号を(0~N-1)の組み合わせを表示するプログラムを作るという問題が手につきません。 ヒントでも良いのでいただきたいです。
C言語関連・17閲覧・50
ベストアンサー
組み合わせの問題は通常「深さ優先探索(DFS)」ですが、この問題には「燃料は使い切らず残っても良い」という条件があるので、DFSのアルゴリズムは不要です。(指定した値と一致となると難しくなります) 燃料が残っもよいので、容量の小さなタンクから容量を加算していけば最大の個数が得られます。
ID非公開
ID非公開さん
質問者
2021/1/21 17:48