0-1ナップザック問題の解き方がわからない

報酬が最大となるタスクの組み合わせを求めよという問題があるサイトで出されました
問題の内容からして動的計画法が使えるのかなと思ったのですが、但し書きで「１度タスクをこなしたら、同じタスクをすることができない」と書いてありました
こういうパターンの場合、どういう風に解いていけばいいんでしょうか
検索したら、ある大学のサイトで0-1ナップザック問題の解き方なるものが出てきましたが、解説を読んでもさっぱりわかりませんでした
アイテムを一つしか使えないナップザック問題を動的計画法で解く方法について教えてほしいです

No.1 ベストアンサー 回答者： Tacosan 回答日時： 2013/08/28 23:49

0-1「でない」ナップサック問題に対する動的計画法が理解できていれば何も問題ないはずなんだけどなぁ....

「とる」か「とらない」かの 2択なんだし.

この回答へのお礼

ありがとうございます
動的計画法で検索したところ、０１ナップザック問題について解説しているサイトが見つかりました
http://algorithms.blog55.fc2.com/blog-category-6 …
解答からどうやってコードにすればいいのかわかりませんが、求めていたものが見つかったので、ベストアンサーとさせていただきます

お礼日時：2013/08/29 15:01