書籍「アルゴリズムとデータ構造」の動的計画法ナップザック問題をpythonで書き換え。分かりにくいインデックス変数を我流に変更

knapsack_algorithm.py

# -*- coding: utf-8 -*-
ITEMS = 5
SIZE = [2, 3, 5, 6, 9]
VALUE = [2, 4, 7, 10, 14]
NAP_SIZE = 16

nap_value = [0] * (NAP_SIZE + 1)

print("ナップザックの大きさ：", end="")
for i in range(1, NAP_SIZE+1):
    print("{0:>2} ".format(i), end="")
print()

# 扱う品物を、１つずつ増やしていく
for item_num in range(ITEMS):
    # ナップザックの大きさが capacity のものに対して
    # 品物 item_num 番を入れてみる
    for capacity in range(SIZE[item_num], NAP_SIZE+1):
        # 品物 item_num 番を入れてみた場合、新しい価値はどう変わるか
        new_value = nap_value[capacity - SIZE[item_num]] + VALUE[item_num]

        if new_value > nap_value[capacity]:
            nap_value[capacity] = new_value

    print("      品物 {}まで使う：".format(item_num+1), end="")

    for j in range(1, NAP_SIZE+1):
        print("{0:>2} ".format(nap_value[j]), end="")
    print()