1、01背包
1.1题面:
1.2思路:
1.3状态转移方程:
每一次从i,j的正上方转移
不放: dp[i][j]=dp[i-1][j];
从上一个物品的同一个容量的最大价值继承过来
放:dp[i][j]=dp[i-1][j-c[i]]+v[i];
2、完全背包
1.1题面:
1.2思路:
1.3状态转移方程:
每一次从i,j的正上方转移
不放: dp[i][j]=dp[i-1][j];
从上一个物品的同一个容量的最大价值继承过来
放:dp[i][j]=dp[i-1][j-c[i]]+v[i];
3、混合背包
3.1 题意
有n个物品,背包容量为m
,第i件物品的费用是cos[i],价值是value[i],每件物品拿p[i]次,求那些物品放入背包总价值最大。
3.2 思路
当p[i]=0时->完全背包
当p[i]=1时->01背包
当p[i]>1时->多重背包
3.3 状态转移方程
3.4 二进制优化
拆成1,2,4,8,……,和剩下的。合并成一个新的物品
4、分组背包
4.1 题意
每组只能拿一个物品。求拿哪些物品放入背包能使得价值最大
4.2 思路
先将不同的物品分类。对每一组物品,用01背包的方式求能拿的最大价值。
4.3 状态转移方程
分组背包_信奥算法题-ACGO题库
滚动数组优化