Day 28 ：0-1背包问题

0-1 背包是一个经典的组合优化问题，其中的思想非常重要。今天我们以一个简单的例子，先来体会 0-1 背包问题。

有一个最大承重量为w的背包，第i件物品的价值为a1[i]，第i件物品的重量为a2[i]，将物品装入背包，求解背包内最大的价值总和可以为多少？

例子：

a1 = [100, 70, 50, 10], a2 = [10, 4, 6, 12], w = 12, 背包内的最大价值总和为 120，分别装入重量为4和6的物品，能获得最大价值为 120

https://blog.csdn.net/qq_38410730/article/details/81667885

https://www.cnblogs.com/kkbill/p/12081172.html

https://blog.csdn.net/mu399/article/details/7722810

https://blog.csdn.net/weixin_41061962/article/details/80319436?utm_medium=distribute.wap_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-7.nonecase&depth_1-utm_source=distribute.wap_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-7.nonecase
理解：
https://blog.csdn.net/m0_37907835/article/details/78991461

背包问题是动态规划的经典问题，可以分为多个子结构，如，

只使用第1个物品在背包容量为1的情况下背包所能装的最大价值：为V[1][1]

只使用第1个物品在背包容量为2的情况下背包所能装的最大价值：为V[1][2]

只使用第1个物品在背包容量为j的情况下背包所能装的最大价值：为V[1][j]

只使用第1,2个物品在背包容量为j的情况下背包所能装的最大价值：为V[2][j]

只使用第1，2,3...i 个物品在背包容量为j的情况下背包所能装的最大价值：为V[i][j]

当使用第 1,2,3,i-1个物品在背包剩余容量为j的情况下，在选第i个物品的时候，如果第i个物品重量大于背包容量，则第i个物品不能放进去 V[i][j] = V[i-1][j]；

否则的话，就可以选择放进去或者不放进去，就要看哪种价值最大 V[i][j] = max(V[i-1][j], V[i-1][j - weight[i]] + value[i])

补全下面代码，返回求解的最大价值：

a1 = [100, 70, 50, 10]
a2 = [10, 4, 6, 12]
W = 12

def f(i, w):
    if  w == 0 or i < 0:
        return 0
    elif a2[i] > w:
        return f(i-1, w)
    return max(a1[i] + f(i-1, w-a2[i]),
               f(i-1, w))

r = f(3,W)
print(r)