完全背包问题

相比于01背包问题
只是单纯的多了一个条件：物品可以重复利用。

这是01背包问题的状态转移方程：

• 当W-wi大于0时，F(n,w) = max(F(n-1,W-wi)+vi,F(n-1,w))
• 当W-wi小于0时，F(n,w) = F(n-1,w))

我们只关注第一个方程，对于完全背包问题，当我们用了第n个物品以后，因为n还可以再次被用，因此其中一个最优子结构F(n-1,W-wi)+vi应该变为F(n,W-wi)+vi，代表用来第n个物品以后，还可以用第n个物品。

对应到代码上，F(n-1,W-wi)代表的是对应的是第 n-1 行的物品中的第W-wi个重量的最大值。对应到代码中就是res_pre中的index为W-wi的值。而F(n,W-wi)对应的就是第n行的物品，就应该是res中的index为W-wi的值
，因此，在01背包问题的代码的基础上，只需要把状态转移方程中的res_pre[w - w_list[n]] + v_list[n]改为res[w - w_list[n]] + v_list[n]即可。

代码实现：

N = 4
W = 10
# v_list = [10,40,30,50]
# w_list = [5,4,6,3]
v_list = [1,5,2,4]
w_list = [2,3,5,7]

#用 一维数组保存中间数据。初始化当只有1个物品的时候，最开始的一维数组。
res_pre = [0]
#注意这里为了与列表中物品的重量一致，需要从1到w+1开始循环
for i in range(1,W+1):
    if i < w_list[0]:
        res_pre.append(0)
    else:
        res_pre.append(v_list[0])

#开始滚动更新一维数组
for n in range(1,N):
    res = [0]
    for w in range(1,W+1):
        if w - w_list[n] < 0:
            res.append(res_pre[w])
        else:
            res.append(max(res[w - w_list[n]] + v_list[n],res_pre[w]))
    # 将新的一行，赋值给res_pre
    res_pre = res
print(res_pre[-1])