Python|动态规划|0-1背包问题
前言
对学算法的同学来说，动态规划是其必学且较为重要的问题之一；其中0-1背包问题是最经典的动态规划问题；本博客也主要以动态规划来解决0-1背包问题。
问题描述
有如下的背包的重量及其所对应的质量，背包的最大承受重量为6kg，试问要怎样装入才能使得背包再最大的承受重量的范围内装入的物品的质量最大？
物品序号 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
重量 | 3kg | 1kg | 2kg | 4kg |
质量 | 6￥ | 10￥ | 5￥ | 10￥ |
动态规划进行问题分析
首先我们的创一个dp[i][j]的数组，bag[index]数组表示物品的重量与质量；
(bag[index][0]表示重量，bag[index][1]表示质量)；其中的i来表示物品，j来表示当前背包所能承受的最大重量；dp[i][j]来表示当前背包重量为j时所能承装的最大质量，这时我们可以等到一个动态的转移方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-bag[index][0]]+bag[index][1]) |
|---|
方程解析；当我们去遍历物品的时候我们会分两种情况，即装与不装；
不装入该物品：dp[i][j]的质量就是上个物品的质量，即就等于dp[i-1][j]；i表示物品，就是i-1的质量。
装入该物品：dp[i-1][j-bag[index][0]]+bag[index][1]，i表示当前的第i个物品，i-1表示上一个物品，因为j表示当前背包所能承装的最大质量，所以j-bag[index][0]表示若要装入物品，那么必须取上一个物品的背包最大容量(即第i-1个物品)为j-bag[index][0]，因为这样装入第i个物品刚好装满容量为j的背包。
代码解决
bag, n, dp = [[6,3],[10,1],[5,2],[10,4]], 6, []# bag表示物品的重量与其所对应的质量，n为背包最大容量for i in range(len(bag)): dp.append([0]*(n+1))for i in range(n+1): if i >= bag[0][1]: dp[0][i] = bag[0][0] #第一次遍历数组将得到第一个物品所对应的最大质量得出for i in range(1,len(bag)): for j in range(n+1): if bag[i][1] <= j: dp[i][j] = max(dp[i-1][j], dp[i-1][j-bag[i][1]]+bag[i][0]) # 取dp[i][j]当前的最大质量print(dp[-1][-1]) # 打印dp最终j=n(背包最大容量)的最大质量 |
|---|
总结
本博客主要讲述了如何用动态规划来解决0-1背包问题；总的来说，0-1背包问题就是经典的动态规划问题，用dp数组来记忆所需的值来推导相关联的下一个值即可。