2019年10月28日月曜日

部分和問題

組み合わせ最適化問題でよく出くわします。解法例は、例えばこちら

例えば、重み3、5,7があり、目的関数値の暫定値が211だったとして、次のターゲットは何になるかを求めるときに使うことがあります。(大抵は、-1すれば済むので、実際はあまり使わない) これを解くには、いわずと知れた動的計画法によるのが一般的です。がナーススケジューリングの場合、そこまでは必要なく、単純なループ探索でも支障がないと思います。  

0 件のコメント:

コメントを投稿

注: コメントを投稿できるのは、このブログのメンバーだけです。