1.背包问题的定义
背包问题是一种组合优化的NP完全问题。
给定一个有限体积的背包和一组物品，每个物品都有自己的重量和价值，求背包可以装载物品的最大价值。
2.背包问题的分类
背包问题根据每种物品可以装载的数量不同，可以分为以下几类：
01背包：每种物品只能装一次：
完全背包：每种物品可以装无限次
多重背包：每种物品可以装载的次数不同
混合背包：前面几种问题的组合
分组背包：给物品分组，每组物品只能选一个。
3.背包问题的求解
背包问题一般使用动态规划求解，在使用动态规划时要明确4步：
- 确定dp数组的含义
- 确定递推公式
- 初始化dp数组
- 确定遍历的顺序
（1）01背包
设背包能装载的最大重量是W,每件物品的重量是wight[i],价值是value[i],每个物品只有一个，问背包可以装载的物品的最大价值。
首先分析问题，若用暴力解法，穷举所有情况，那么每件物品都有选或不选不选两种状态，计算下来就是
O
(
n
3
)
O(n^3)
O(n3)的时间复杂度，因为时间复杂度过高，所以一般用动态规划求解。
01背包的求解
第一步：确定dp数组
一般使用二维数组dp[i][j]求解01背包问题，dp[i][j]表示在下标0-i的物品中选择，容量为j的背包可以装载的最大价值。
第二步：确定递推公式
当选中当前物品时，因为放下i后当前容量不超过j，所以当前dp[i][j]的上一个状态容量为j - weight[i]，这样在放下i后才能保证当前容量不超过j;当不选中当前物品时，上一个状态的容量最大可以还是j，因此递推公式为：
d
p
[
i
]
[
j
]
=
m
a
x
(
d
p
[
i
−
1
]
[
j
−
w
e
i
g
h
t
[
i
]
]
+
v
a
l
u
e
[
i
]
,
d
p
[
i
−
1
]
[
j
]
)
（
1
）
dp[i][j] = max(dp[i - 1][j - weight[i]] + value[i], dp[i - 1][j]) （1）
dp[i][j]=max(dp[i−1][j−weight[i]]+value[i],dp[i−1][j])（1）
第三步：初始化dp数组
因为容量为0时可以装载的最大价值为0，所以dp[i]][0] = 0
第四步：确定遍历的顺序
按公式（1），既可以现遍历i，也可以先遍历j，但是01背包中为了因为i只与i-1有关，可以用滚动数组优化，所以先遍历i。
初始Java代码
public static int test_01_bag(int volumn, int[] weight, int[] value) {
int[][] dp = new int[weight.length][volumn.length + 1];
for(int i = 1; i < weight.length; i++)
for(int j = 1; j < = volumn; j++) {
if(j < weight[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
return dp[weight.length - 1][volumn];
}
public class Main {
public static void main(String[] args) {
int[] weight = {1,2,4};
int[] value = {30,35,40};
int volumn = 6;
int max_value = test_01_bag (volumn, weight, value);
}
}
优化Java代码
/*
因为i只和i-1有关，所以可以使用滚动数组优化
*/
public class Main {
public static int test_01_bag_opt(int volumn, int[] weight, int[] value) {
int[] dp = new int[volumn + 1];
for(int i = 0; i < weight.length; i++)
for(int j = volumn; j > = weight[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
return dp[volumn];
}
public static void main(String[] args) {
int[] weight = {1,2,4};
int[] value = {30,35,40};
int volumn = 6;
int max_value = test_01_bag_opt (volumn, weight, value);
}
}
组合问题
组合问题和01背包有一定差别，组合问题是求有多少种装载方法，而不是求装载的最大价值。组合问题的递推公式一般为dp[i][j] = dp[i - 1][j] + dp[i - 1][j - weight[i]]。
经典例题
leetcode 416分割等和子集
leetcode 1049最后一块石头的重量2
（2）完全背包
完全背包与01背包唯一不同的地方就是每种物品可以装载无限次。
完全背包的求解
完全背包的求解和01背包相似，递推公式完全一样。不同的是遍历顺序。
在01背包中，如果使用二维dp，遍历顺序是任意的，如果使用一维dp，遍历顺序必须是先遍历物品，再遍历容量，且容量必须从大到小遍历。
在完全背包中，如果使用一维dp，遍历顺序是随意的，但是对于容量必须从小到大遍历。
Java代码
public class Main {
public static int test_complete_bag_opt(int volumn, int[] weight, int[] value) {
int[] dp = new int[volumn + 1];
for(int i = 0; i < weight.length; i++)
for(int j = weight[i]; j <= volumn; j++) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
return dp[volumn];
}
public static void main(String[] args) {
int[] weight = {1,3,4};
int[] value = {15,20,30};
int volumn = 4;
int max_value = test_complete_bag_opt(volumn, weight, value);
System.out.println(max_value);
}
}
完全背包的组合问题和排列问题
如果是求组合问题，先遍历物品，再遍历容量；如果是求排列问题，先遍历容量，再遍历物品
经典例题
leetcode518:零钱兑换II
leetcode322:零钱兑换
leetcode377:组合总和IV
leetcode279:完全平方数