SHIINBLOG

Python で ナップサック問題 を 総当たりで解く

Python3 でナップサック問題を総当たりで解くプログラムを書く機会があったので.

ナップサック問題総当たり

ナップサックに入れるか入れないかを2進数で判断している. 入れるなら 1 , 入れないなら 0 となる.

品物が15だとしたら,15ビットの2進数だと考えられる.
そこで,10進数の「0〜32767」 までを調べる.
2進数では 000000000000000 〜 111111111111111

それで,全ての組み合わせを求めることができる.