01背包完全背包学习记录
背包问题
- 前言
- 一、01背包
- 1、花样滑冰
- 2、二维递推
- 二、完全背包
- 1、花样滑冰（可选择相同动作）
- 2、解
- 3、完全平方数
- 4、解
- 总结
- 参考文献
前言
背包问题是动态规划的一类，背包又分01背包 & 完全背包，各自有各自很鲜明的特点，虽同为背包，形式也很像，但是细节上很大不同。
一、01背包
01表示面对数组的每一个值（抽象），每个值只能取一次或者不取，此时的状态应该是二维的，不仅外层递推target，内层还需递推数组取当前值和不取当前值。
1、花样滑冰
一个运动员有energy的能量，可选择跳不同的动作actions[m][2]，actions[i][0]表示第i个动作要消耗的能量，actions[i][1]表示第i个动作得到的分，要求不能做同样的动作，问：运动员能得到的最大分数是多少？
2、二维递推
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* <p>
* 运动员可得到的最高分
*
* @param energy int整型 运动员体力值
* @param actions int整型二维数组 二维数组i为动作号 actions[i][0]为动作i+1消耗体力,actions[i][1]为动作i+1得分
* @return int整型
*/
public int maxScore(int energy, int[][] actions) {
int n = actions.length;
int[][] f = new int[energy + 1][n + 1];// 体力为i前j的最大得分。
for (int i = 1; i <= energy; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = f[i][j - 1];
if (actions[j - 1][0] <= i)
f[i][j] = Math.max(f[i][j], f[i - actions[j - 1][0]][j - 1] + actions[j - 1][1]);
}
}
return f[energy][n];
}
二、完全背包
完全表示面对数组的每一个值（抽象），每个值可以取多次，所以不存在当前值是否取或不取，虽也需要for循环寻找最值，但意义完全不一样。
1、花样滑冰（可选择相同动作）
如果能选择同样的动作，则问题变为完全背包问题。
2、解
// 动作可重复，完全背包。
public int maxScore2(int energy, int[][] actions) {
int n = actions.length;
int[] f = new int[energy + 1];// 体力为i的最大得分。
for (int i = 1; i <= energy; i++) {
for (int j = 1; j <= n; j++) {
if (actions[j - 1][0] <= i)
f[i] = Math.max(f[i], f[i - actions[j - 1][0]] + actions[j - 1][1]);
}
}
return f[energy];
}
3、完全平方数
4、解
public int numSquares(int n) {
int[] f = new int[n + 1];
for (int i = 1; i <= n; i++) {
f[i] = Integer.MAX_VALUE;
for (int j = 1; j * j <= i; j++) {
f[i] = Math.min(f[i], f[i - j * j] + 1);
}
}
return f[n];
}
总：这两完全背包有一些细微的区别，就是数组是否有序问题，可以剪枝。
总结
1）如果能对问题进行分类，才算看到了区别和细节，才算入了门。
2）01背包特指只能装一个/不装，就必须进行二维递推，不仅要递推target，还要递推取不取当前+前n-1的状态应该是前面的最值。
3）完全背包指一种东西可以装很多次，此时直接递推target即可，里面套for循环寻找最值。
4）两种背包虽然同套for循环，但一种是二维递推，一种是面向整个数组寻找最值。
参考文献
[1] LeetCode 完全平方数