ナップサック問題

Tweet

https://www.itmedia.co.jp/enterprise/articles/1005/15/news002.html
を参考に動的計画法のひな型を書いてみた。
動くには動くが、何かコードが複雑。
もっとシンプルに書けないか検討する。

# coding:UTF-8
from copy import copy

W = 14

def create_pattern(memo, w, v):
    pattern = [0 for _ in range(W)]

    is_first = True

    for data in memo:
        if data != 0:
            is_first = False

    if is_first:
        pattern[w] = v
        return pattern

    for memo_w, memo_v in enumerate(memo):
        if memo_v != 0 or memo_w == 0:
            # vを選ばない
            if pattern[memo_w] < v:
                pattern[memo_w] = memo_v

            # vを選ぶ
            comb_v = memo_v + v
            comb_w = memo_w + w
            if pattern[comb_w] < comb_v:
                pattern[comb_w] = comb_v
        elif memo_w == w:
            pattern[memo_w] = v

    return pattern

if __name__ == '__main__':
    #(重さ, 価値)のリスト
    goods = [(3, 2),
             (4, 3),
             (1, 2),
             (2, 3),
             (3, 6)]

    # 全部の組み合わせを考える
    # それぞれ選ぶかどうかであるから、
    # 1を鞄に入れる、0をカバンに入れないとすると
    """
    patterns = [
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],        # 何も選ばない
        [0, 0, 0, 30, 0, 0, 0, 0, 0, 0, 0, 0],       # 3だけの組み合わせ
        [0, 0, 0, 30, 50, 0, 0, 80, 0, 0, 0, 0],     # 3と5の組み合わせ
        [0, 0, 0, 30, 50, 60, 0, 80, 90, 110, 0, 0], # 3と5と6の組み合わせ
    ]
    """

    patterns = [[0 for _ in range(W)]]

    for i, good in enumerate(goods):
        memo = patterns[i]
        w = good[0]
        v = good[1]
        new_pattern = create_pattern(memo, w, v)
        patterns.append(new_pattern)

    for p in patterns:
        print(p)

基本的にmemoの配列の値が0以外であれば、その値との組み合わせを考えればよいのだが、初期のすべて選ばない、を考慮するため20行目のmemo_w == 0が必要になり、これが汚く感じさせる。
つまり、境界だけ特殊な処理が必要というのがダサい。