动态规划求解背包问题

问题描述

有n个物品， 每个物品有各自的重量，价值。请在限定承重下求出总价值最大的组合。

物品编号	0	1	2	3	4
价值	12	45	23	16	16
重量	5	12	11	6	4

在限重23的情况下， 最佳方案是1，3， 4. 总价值为77. 当然，若每个物品可选择不止1次（即完全背包）则为4个4号， 1个3号， 总价值80.

为什么是上面的答案？

对于物品i，剩余重量j的情况下，最大价值
也就是说，对于物品i， 要么选，要么不选，比较做出选，不选两种决定后的总价值，取最大者，就能得到解

递归写法

递归更容易理解上面的思路

v = [12, 45,23, 16, 16]
w = [5, 12, 11, 6, 4]

def fun(i, j):
    if i ==0 or j ==0:
        return 0
    if  j-w[i-1] >= 0: 
        return max(fun(i-1, j), fun(i-1, j-w[i-1]) + v[i-1])
    else:
        return fun(i-1, j)  #剩余重量无法放下
fun(5, 23)

77

非递归写法

实际上，递归是比较慢，且浪费空间的一种做法，很多被重复计算了

"""
@author: 追上我的速度@QTK
"""
def bag_problem(v, w, max_w, kind='01'):
    size = len(v)
    result = init_array(size + 1, max_w + 1)
    rec = init_array(size + 1, max_w + 1)
    for i in range(1, size + 1):
        for j in range(1, max_w + 1):
            if kind == '01': #最多只能挑1件
                end = 2
            else: #完全背包
                end = j // w[ i - 1] + 1
            for k in range(end):
                if j - k * w[i-1] >= 0
                    and result[i][j] < result[i-1][j - k * w[i-1]] + k * v[ i -1]:
                    result[i][j] = result[i-1][j - k * w[i-1]] + k * v[ i -1]
                    rec[i][j] = k
    #至此，result[-1][-1]为最大价值

    #输出选择
    i, j = size, max_w
    while i:
        print('{} : {}'.format(i - 1, rec[i][j]))
        j -= w[i - 1] * rec[i][j]
        i -= 1

    return result[-1][-1]

#0-1
4 : 1
3 : 1
2 : 0
1 : 1
0 : 0
77

#完全
4 : 4
3 : 1
2 : 0
1 : 0
0 : 0
80