背包问题有部分背包问题、01背包问题、完全背包问题、多重背包问题以及混合背包问题等几种，其中01背包是最为基础的，理解全了01背包问题，其他的背包问题都迎刃而解。
有N件物品和一个容量为M的背包，设第i件物品的费用(体积重量)是w[i]，价值是c[i]。求解如何选择物品可以使得费用(体积重量)总和不超过背包容量V，且价值最大。
01背包的特点：每种物品只有一件，可以选择放或不放
01背包状态分析
首先复习一下动态规划的核心思想：将每个状态的最优值记录下来
状态设置：设f[i][v]表示前i个物品放入一个容量为v的背包所获得的最大价值
只需考虑背包容量为v时，物品的放置情况如下（先理思路，图在后面，要耐心看哦）：
(1)第i件物品的策略(放或不放)
放的状态：就是前i-1件物品在背包容量v-w[i]时的最优解+当前物品的价值c[i]，也就是f[i-1][v-w[i]]+c[i]
不放的状态：就是前i-1件物品在背包容量同样为v时的最优解，也就是f[i-1][v]
(2)另一种情况：第i件物品的费用大于背包容量，根本放不进状态为：f[i-1][v]
01背包状态转移方程
如果第i件物品能放入背包中(w[i] <= v)则状态转移方程为:
如果第i件物品不能放入背包中(w[i] > v)则状态转移方程为：
最终的最优解就是f[N][M] (有N件物品和一个容量为M的背包)
01背包基本思路
阶段数：由N件物品的数目,和背包容量M共同确定的
状态：设f[i][v]表示前i个物品(全部物品或者部分物品)放入一个容量为v的背包可以获得的最大价值
边界条件：f[0][v]=0，f[i][0]=0没有物品放入最大价值为0
注意：这里的v是会变化的v=(0...M)
01背包动态规划基本思路
举一个例子我们一起来分析下：
假设有分别a、b、c的三件物品，费用分别是2、3、4，价值分别是1、3、5现在给你承重为8的背包，如何让背包里的物品具有最大价值。
首先放a物品：
所以同理可以得到在背包容量从0~8的时候，物品a放入背包的剩余情况最优解。
接着放物品b，和放a物品差不多。
需要注意的是，当背包容量为3的时候：不放物品b的最大价值为f[i][v] = f[i-1][v] = 1；但是放入b的价值为f[i][v] = f[i-1][v-w[i]] + c[i] = 3，所以此时最大价值为3。
当背包容量为8时，放入b后，此时f[2][8]的最大价值为4。
接着继续放物品c。
最后得到在背包容量为8的时候，最大价值为8.
01背包模板题
一个旅行者有一个最多能装M公斤的背包，现在有N件物品，它们的重量分别是W1,W2,......Wn,它们的价值分别为C1，C2......Cn求旅行者能获得最大总价值的物品？
输入格式：
第一行：两个整数，M背包容量M<=200,N物品数量N<=30
第二行至N+1行：每行两个整数Wi, Ci表示每个物品的重量和价值
输出格式：
仅一行，一个数表示最大总价值
输入样例：
10 4
2 1
3 3
4 5
7 9
输出样例：
12
模板题解析
1. 确定阶段数
就是N件物品的数目,和背包容量M共同确定的
2. 确定状态
设f[i][v]表示前i种物品(全部物品或者部分物品)放入一个容量为v的背包可以获得的最大价值
3. 确定状态转移方程和边界
放的进：f[i][v] = max{f[i-1][v], f[i-1][v-w[i]] + c[i]}
放不进：f[i][v]=f[i-1][v]
边界条件：f[0][v] = 0 , f[i][0] = 0
4. 程序实现
根据f[v]=max{f[v],f[v-w[i]]+c[i]}，放第i个物品可以发现只与前i-1个物品的状态有关
放入a物品后，更新一维数组，见下图。
放入b物品后，更新一维数组，见下图。
放入c物品后，更新一维数组，见下图。
可得状态转移方程： f[v]=max(f[v],f[v-w[i]]+c[i])
注意：v值越小的越迟被覆盖，由于要被调用运算。即按v倒序运算
01背包动态规划改进解法分析（一维数组）
1、确定阶段数
就是N 件物品的数目,和背包容量 V共同确定
2、确定状态
设f[v]表示前i种物品(全部物品或者部分物品)放入一个容量为v的背包可以获得的最大价值
3、确定状态转移方程和边界
f[v]=max(f[v],f[v-w[i]]+c[i])
边界条件 f[0] = 0
4、程序实现
给大家提供一个自己搭建的HustOj，目前在逐渐加题中，有兴趣的话可以去看看，搜索自己想要的题目~
网址：http://120.26.142.136/ 或者 wmast.cn
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/14951.html