osanine https://blog.hatena.ne.jp/osanine/ ようじょと結婚したい https://osanine.hatenadiary.org/ アルゴリズム C 0-1ナップザック問題のDPのデータフローの図[1]を見ていたら、計算機実験[2]の時にやった並列化が適用出来そうだなあと思ったので実装してみました。 並列化の方法としては、DPの配列R[品物][容量]に対して大きく (1)列を各スレッドで分割 (2)行を各スレッドで分割 (3)行列をブロックに分割 の3つに分けられます。 (1)は1つの列(容量)を複数のスレッドで分担して、1行ずつ同期をとって処理をしていきます。 同じ行内ではデータの依存関係がないので1行につき1回の同期を取るだけでいいので楽です。 (2)は行(品物)ごとにスレッドで分割するのですが、行同士は依存関係があります。 具体的には… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fosanine.hatenadiary.org%2Fentry%2F20100830%2F1283167777" title="0-1ナップザック問題を並列化する - ようじょと結婚したい" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2010-08-30 20:29:37 rich https://osanine.hatenadiary.org/entry/20100830/1283167777 1.0 100%