asaのブログ

プログラミングの勉強まとめ

DPL_1_B ナップザック問題

 ゼミの教科書に出ていてどんな問題か気になっていたナップザック問題の近似解が解けました。NP困難な問題として知られるナップザック問題ですが、貪欲法ではなく動的計画法で解くことで近似解をだすことができます。

 

 N個の品物についてナップザックに入れる入れないを全て調べると2のN乗の計算量がかかりますが、動的計画法を使うことで重さWとしたときNWで求めることができます。参考書は例によってこれ。

 

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

 

 

 コード

gist1efd241fd2079a22fd7a6147a4348e98