01背包问题

题目描述：
给定 n 个物品和一个容量为 W 的背包，物品 i 的重量是 wi，其价值为 vi 。
应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？
（输出给定n和W时的最大总价值）

题目解析：这道题跟动态规划_实战1中的国王与金矿问题是一样的。物品不能重复用。

写出状态转移方程以后，分析如何构造一个一维数组保存中间数据，然后滚动更新该一维数组 即可。

——————————————————————————————————

需要注意的地方

1、物品的顺序是固定的

同国王与金矿的问题一样，我们认为，物品的顺序是固定的，这样 才能够合理的写出最优子结构。

2、要考虑背包重量为0的情况（即使题目说了背包重量大于0）

我们假设F(n,w)代表物品为第n件结尾，背包空间为w时，所能够装下的最大价值。
那么，F(1,0)也是一定要存在的，表示只有一一个物品，但承重为0的情况！

因为在最优子结构中，可能会出现F(n-1,W-wi)+vi中，W-wi等于0的情况，此时前面的F(n,0)的值也应该为0，
此时，最有子结构的值就等于后面的被加数vi了。

因此，在构造一维数组时，需要初始化为res=[0]，再陆续添加重量为1,2，...，w的情况。（其实在国王与金矿构造的一维数组中，也需要考虑人数为0的情况的。）

3、构造数组时，要注意与重量列表中的重量一致

表现在代码上:

for i in range(1,W+1):

4、状态转移方程

• 当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))
  先初始化一行，然后进行两个for循环，不断地滚动这两行，一直到最后的结果

代码实现：

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_pre[w - w_list[n]] + v_list[n],res_pre[w]))
    # 将新的一行，赋值给res_pre
    res_pre = res
print(res_pre[-1])