Pythonでナップサック問題 – taichino.comナップサック問題とかメジャーなアルゴリズムすら綺麗さっぱり忘れてて困ります。リハビリにwikipediaを見ながらPythonで書いてみました。 ナップサック問題はn個の商品(それぞれ重さwと価値v)がある時に、キャパシティC以内の制約条件の元で最良の組合せを見つけるというものです。 それぞれの商品を１回しか選べない場合は、0-1ナップサック問題、複数回選択可能な時は123ナップサック問題と呼ばれていてアルゴリズムも違います。それぞれ書いてみたのが以下になります。 #!/usr/bin/python # -*- coding: utf-8 -*- # reference: http://en.wikipedia.org/wiki/Knapsack_problem # 0-1 ナップサック問題 (2次元動的計画法) # items = [{'w':weight, 'v':value}, {.
