0-1背包问题（学习笔记）

一名不敲代码的不合格的CS学生，之前做一个比赛时要用到01背包算法，当时看了一下没看懂居然放弃了。最近算法分析课程正在讲动态规划，01背包问题还是没太听明白，看了一下博客明白看懂了。所以简单的做一下学习笔记。

最开始针对一个具体问题，我们要先弄弄输入输出是时候，对于01背包问题输入很简单，输入就是w[n]数组和v[n]数组，分别对应n件物品的重量和价值，还有一个就是背包的最大容量。

为了解决01背包问题，我们定义了一个m[n][c]数组，其中任意一个元素m[i][j]代表了在处理第i件物品时，背包的当前可用容量为j时的可产生的最大价值。

因此任意1<=i<=n对应了两种情况,

if w[i]>j
   m[i][j] = m[i-1][j]//背包装不下第i件物品
else
   m[i][j] = max(m[i-1][j], m[i-1][j-w[i]]+v[i])//背包可装下第i件物品

这是一个求m[i][j]的一个递推公式，如果你好好看看一个具体的m[i][j]矩阵，你就能明白了，而最后m数组的最后一个元素m[n][c]一定是背包容量为C所能承载物品的最大价值。

秒客网