欢迎点击「算法与编程之美」↑关注我们！

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

欢迎加入团队圈子！与作者面对面！直接点击！

前言

对学算法的同学来说，动态规划是其必学且较为重要的问题之一；其中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数组来记忆所需的值来推导相关联的下一个值即可。

END

编 辑 | 王 文 星

责 编 | W Z Y

能力越强，责任越大。实事求是，严谨细致。

——where2go 团队

---

微信号：算法与编程之美

长按识别二维码关注我们!

温馨提示：点击页面右下角“写留言”发表评论，期待您的参与！期待您的转发！