01背包与完全背包问题
1.递归解法
public static int knapsack(int capacity, int[] weights, int[] values) {
int n = weights.length;
//递归的套路，加一个index索引，控制递归到了哪一层
return bestValue(capacity,n-1,weights,values);
}
private static int bestValue(int capacity, int index, int[] weights, int[] values){
//递归的第一步：终止条件，没有商品了或者背包没容量了就终止
if(index <= 0 || capacity<= 0){
return 0;
}
//不放的情况
int res = bestValue(capacity,index-1,weights,values);
//放的情况，需要剩余满足容量>=weights[index]
if(capacity >= weights[index]){
//放的情况为bestValue(capacity - weights[index],index-1,weights,values)。也就是index放进去。其他的容量放
//前面index-1
res = Math.max(res,values[index]+bestValue(capacity - weights[index],index-1,weights,values));
}
return res;
} 递归解法存在大量的重复计算。导致效率不高。下面可以进一步优化。
--------------------------------------------------------------------------------------------
2.记忆搜索解法。
申请一个二维数组用来记录重叠子问题。用空间换时间。
public static int knapsack(int capacity, int[] weights, int[] values) {
int n = weights.length;
//因为有商品和价值两个维度，所以需要用一个二维的空间来记录
memo = new int[n][capacity+1];
for (int i = 0; i < n; i++) {
for (int j = 0; j <= capacity ; j++) {
memo[i][j] = -1;
}
}
return bestValue(capacity,n-1,weights,values);
}
private static int bestValue(int capacity, int index, int[] weights, int[] values){
//递归的第一步：终止条件，没有商品了或者背包没容量了就终止
if(index <= 0 || capacity<= 0){
return 0;
}
//如果已经有缓存，直接从缓存中取即可，避免重复计算
if (memo[index][capacity] != -1){
return memo[index][capacity];
}
//不放的情况
int res = bestValue(capacity,index-1,weights,values);
//放的情况，需要剩余满足容量>=weights[index]
if(capacity >= weights[index]){
//放的情况为bestValue(capacity - weights[index],index-1,weights,values)。也就是index放进去。其他的容量放
//前面index-1
res = Math.max(res,values[index]+bestValue(capacity - weights[index],index-1,weights,values));
}
//将计算的结果加入缓存
memo[index][capacity] = res;
return res;
} 记忆搜索虽然在时间复杂度上已经满足要求，但是递归需要大量堆栈上的空间，容易造成栈溢出。最好能将递归转换成递推。
==========================================================================
3.动态规划解法。动态规划其实就是一个填表的过程。下面举个例子说明整个过程。
假设有一个容量为5的背包以及3个物品
申请一个二维表格dp，并将第一行和第一列初始化。初始化的规则为。
对于第一行，第一行表示只有一个物品。所以只要capacity >= weights[0]，就初始化为values[0]。
对于地理列，第一列表示背包容量为0的时候，所以第一列的值都为0
然后填dp[1][1]
public static int knapsack(int capacity, int[] weights, int[] values) {
assert (weights.length == weights.length);
int len = weights.length;
if(len == 0){
return 0;
}
//dp表示i个物品放进容量为c的背包的效益
int[][] dp = new int[len][capacity+1];
//初始化第一列，第一列表示背包容量为0的时候，所以第一列的值都为0
for (int i = 0; i < len ; i++) {
dp[i][0] = 0;
}
//初始化第一行。第一行表示只有一个物品。所以只要capacity >= weights[0]，就初始化为values[0]
for (int i = 1; i <= capacity ; i++) {
dp[0][i] = capacity >= weights[0]?values[0]:0;
}
for (int i = 1; i < len ; i++) {
for (int j = 1; j <= capacity ; j++) {
//第i个物品放不时的结果，和只有i-1个物品的结果一样
dp[i][j] = dp[i-1][j];
//第i个物品能放下
if(j >= weights[i]){
//比较放和不放哪种能产生更高的价值
dp[i][j] = Math.max(dp[i][j],values[i]+dp[i-1][j-weights[i]]);
}
}
}
return dp[len-1][capacity];
} =======================================================================
4.空间压缩。从填表的过程可以看出。其实每次只依赖上一行。因此用一个2行的数组即可表示整个过程。
public static int knapsackDp(int capacity, int[] weights, int[] values) {
assert (weights.length == weights.length);
int len = weights.length;
if(len == 0){
return 0;
}
//dp表示i个物品放进容量为c的背包的效益
int[][] dp = new int[2][capacity+1];
for (int i = 0; i < 2 ; i++) {
dp[i][0] = 0;
}
for (int i = 1; i <= capacity ; i++) {
dp[0][i] = capacity >= weights[0]?values[0]:0;
}
for (int i = 1; i < len ; i++) {
for (int j = 1; j <= capacity ; j++) {
dp[i%2][j] = dp[(i-1)%2][j];
//第i个物品能放下
if(j >= weights[i]){
dp[i%2][j] = Math.max(dp[(i-1)%2][j],values[i]+dp[(i-1)%2][j-weights[i]]);
}
}
}
return dp[(len-1)%2][capacity];
} =================================================================
5.空间继续压缩。用一行也可以。
public static int knapsack(int capacity, int[] weights, int[] values) {
assert (weights.length == weights.length);
int len = weights.length;
if(len == 0){
return 0;
}
//dp表示i个物品放进容量为capacity的背包的效益
int[] dp = new int[capacity+1];
//只放第0个物品，只有能放下。产生的价值就是values[0]，否则为0
for (int i = 0; i <= capacity ; i++) {
dp[i] = i >= weights[0]?values[0]:0;
}
for (int i = 1; i < len ; i++) {
//注意一定为倒序，j < weights[i]的话，表示放不下了。那么可以终止循环。这是动态规划中
//一个常用的做法。减枝
for (int j = capacity; j >= weights[i]; j--) {
dp[j] = Math.max(dp[j],values[i]+dp[j-weights[i]]);
}
}
return dp[capacity];
} 为什么要强调递推过程是逆序的呢？
举个例子
假设n=1，背包容量c=5，只有一个物品，w和v都为1，倒着推得结果为
0 1 2 3 4 5
1 0 1 1 1 1 1
正着推得结果为
0 1 2 3 4 5
1 0 1 2 3 4 5
其实正向递推为完全背包。
因为倒着推。每个物品只有一次选择的机会，放或者不放。
正向推。每个物品在每次都可以选择放或者不放。所以是完全背包。
完全背包代码如下
public static int knapsack(int capacity, int[] weights, int[] values) {
assert (weights.length == weights.length);
int len = weights.length;
if (len == 0) {
return 0;
}
//dp表示i个物品放进容量为capacity的背包的效益
int[] dp = new int[capacity + 1];
for (int i = 0; i < len; i++) {
//必须满足容量>=weights[i]才能放入
for (int j = weights[i]; j <= capacity; j++) {
dp[j] = Math.max(dp[j], values[i] + dp[j - weights[i]]);
}
}
return dp[capacity];
} 一些背包问题相关的算法题解析请参考此博文
