動的計画_01リュックの問題(python実装)(pythonテンプレート)

0-1リュックサックの問題:1組の物品を与えて、すべての物品はすべて自分の重量と価格があって、制限の総重量の中で、私達はどのように選択して、物品の総価格を最も高くすることができます.ここにpythonのテンプレートを記録します

def dp(weight, count, weights, costs):
    """
          ，     O(weight * count),      O(weight)
    :param weight:          
    :param count:     
    :param weights:        
    :param costs:        
    :return:          
    """
    preline, curline = [0] * (weight + 1), [0] * (weight + 1)
    for i in range(count):
        for j in range(weight + 1):
            if weights[i] <= j:
                curline[j] = max(preline[j], costs[i] + preline[j - weights[i]])
        preline = curline[:]
    return curline[weight]


# count：    ； weight：     ； costs：        ； weight：       
count, weight = 5, 10
costs = [200, 300, 350, 400, 500]
weights = [3, 4, 3, 5, 5]
print(dp(weight, count, weights, costs))

#    900
#         
# 0 0 0 200 200 200 200 200 200 200 200
# 0 0 0 200 300 300 300 500 500 500 500
# 0 0 0 350 350 350 550 650 650 650 850
# 0 0 0 350 350 400 550 650 750 750 850
# 0 0 0 350 350 500 550 650 850 850 900