syou6162 https://blog.hatena.ne.jp/syou6162/ yasuhisa's blog https://www.yasuhisay.info/ アルゴリズム 離散最適化 Python どういうときに何ができるのかについて。この辺見ながら。問題定義品物がN個あったとする。品物iには価値と体積が与えられている。は1のとき品物iを取る、0のときに取らないということを表すバイナリ変数であるとする。持って行ける品物の総体積がbまでであるとすると、ナップサック問題は以下の最適化問題として定式化される。 最大化: 制約: かつ これを真面目に列挙して解こうとするとO(2^N)となって多項式時間では解けない。の部分をという風に連続緩和してやれば解は閉じた形で書き表すことができる(でソートしてやって、でかい順に詰めていく。最後のやつは入る分だけ詰める)。動的計画法ここで、体積とbを「整数」で… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fwww.yasuhisay.info%2Fentry%2F20110321%2F1300657815" title="ナップサック問題について整理 - yasuhisa&#39;s blog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://ecx.images-amazon.com/images/I/41CsP6OIB7L.jpg Hatena Blog https://hatena.blog 2011-03-21 06:50:15 rich https://www.yasuhisay.info/entry/20110321/1300657815 1.0 100%