python实现：验证0-1背包问题的动态规划算法

要求自己设计使用合适的数据结构，用于存储计算过程中各个子问题对应的最优子集，以方便最后进行回溯，生成最终问题的最优子集组成元素。

def bag(n, c, w, v):
    # 保存状态
    value = [[0 for j in range(c + 1)] for i in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, c + 1):
            value[i][j] = value[i - 1][j]
            if j >= w[i - 1] and value[i][j] < value[i - 1][j - w[i - 1]] + v[i - 1]:
                value[i][j] = value[i - 1][j - w[i - 1]] + v[i - 1]
    return value
z
def show(n, c, w, value):
    print('最大价值为:', value[n][c])
    x = [False for i in range(n)]
    j = c
    for i in range(n, 0, -1):
        if value[i][j] > value[i - 1][j]:
            x[i - 1] = True
            j -= w[i - 1]
    print('背包中所装物品为:')
    for i in range(n):
        if x[i]:
            print('第', i+1, '个,', end='')

n = 4  #物品数量
c = 5  #容量
w = [2, 1, 3, 2]  #物品重量
v = [12, 10, 20, 15]  #物品价值
value = bag(n, c, w, v)
for _ in value:
    print(_)

show(n,c,w,value)