- ベストアンサー
0-1ナップザック問題の解き方がわからない
報酬が最大となるタスクの組み合わせを求めよという問題があるサイトで出されました 問題の内容からして動的計画法が使えるのかなと思ったのですが、但し書きで「１度タスクをこなしたら、同じタスクをすることができない」と書いてありました こういうパターンの場合、どういう風に解いていけばいいんでしょうか 検索したら、ある大学のサイトで0-1ナップザック問題の解き方なるものが出てきましたが、解説を読んでもさっぱりわかりませんでした アイテムを一つしか使えないナップザック問題を動的計画法で解く方法について教えてほしいです
noname#185852
- その他（プログラミング・開発）
- 回答数1
- ありがとう数2
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
0-1「でない」ナップサック問題に対する動的計画法が理解できていれば何も問題ないはずなんだけどなぁ.... 「とる」か「とらない」かの 2択なんだし.
お礼
ありがとうございます 動的計画法で検索したところ、０１ナップザック問題について解説しているサイトが見つかりました http://algorithms.blog55.fc2.com/blog-category-6.html 解答からどうやってコードにすればいいのかわかりませんが、求めていたものが見つかったので、ベストアンサーとさせていただきます