＜集大成＞アルゴリズム大辞典

＜集大成＞アルゴリズム大辞典 at TECH

485:デフォルトの名無しさん
08/09/23 09:49:23
>>480
状態を (現在の重さ，最後に入れた重さ，現在の価値) という三つ組みで持つ．

重さが自然数であれば，品数を n，重さの最大値を W としたとき
普通の動的計画法に基づく O(n W) アルゴリズムを修正すれば
O(n^2 W) のアルゴリズムが簡単に作れる．

重さが実数であれば，基本的には枝刈り探索しかないのだから，
上の三つ組みを持って適当に探索する．
本気を出すなら，品数や重さなどによって適切な探索法が変わるけど
そこまでがんばるかい？

次ページ

続きを表示

1を表示