背包九讲1之01背包
九个问题
01背包
完全背包
多重背包
混合背包
二维混合背包
分组背包
背包问题求方案熟
求背包问题的方案
有依赖的背包
感谢： https://www.youtube.com/watch?v=nleY0-eexps
01背包
问题描述
问题描述
有N件物品和一个容量V的背包，第i件物品体积vi，价值是wi.
求解将那些物品装入背包，可是这些物品总体积不超过背包容量，且总价值最大
输入格式
第一行两个整数, N和V, 用空格隔开, 分别表示物品数量和背包容积
接下来有N行, 每行有两个整数vi, wi, 分别表示第i件物品的体积和价值
输出格式
一个整数, 表示最大价值
数据范围
0 < N, V <1000
0 < vi, wi < 1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例
8
算法分析
我们用一个二维数组f[n][m]存储所有状态，n表示商品总数，m表示背包容量。m,n > 0
f[i][j]表示只考虑前i个物品，总体积是j的情况下，总价值最大是多少
i,j取值范围 0<i<=n, 至少一个商品，之多n个商品; 0<=j<=m，重量最小可以是0(刚好用完)，最大可以是m
如何求解f[i][j]? 对于每一个f[i][j], 我们哟两种选择, 不选择它或者选泽它。
不选第i个商品...
