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-1res = 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-1res = 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的时候，所以第一列的值都为0for (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]，否则为0for (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];}

一些背包问题相关的算法题解析请参考此博文

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！