一、总述
在动态规划中,01背包和完全背包可以说是动态规划最典型的应用了。先介绍一下定义:
动态规划:英⽂:Dynamic Programming,简称DP,动态规划是一种多阶段决策最优解模型的思想,如果某⼀问题有很多重叠⼦问题,使⽤动态规划 是最有效的。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些字问题的解得到原问题的解。
01背包:有N件物品和⼀个最多能被重量为W 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每 件物品只能⽤⼀次,求解将哪些物品装⼊背包⾥物品价值总和最⼤。
完全背包:有N件物品和⼀个最多能被重量为W 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每 件物品可以无限使用,求解将哪些物品装⼊背包⾥物品价值总和最⼤。
二、01背包详解
题目:有N件物品和⼀个最多能背重量为W 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每 件物品只能⽤⼀次,求解将哪些物品装⼊背包⾥物品价值总和最⼤。
解释:我们知道动态规划就是把大问题划分为小问题,先求出小问题的解,然后在通过小问题的解求出大问题的解,所以我们先要用一个数据结构来保存小问题求出的解,这样才好根据保存的解求出大问题的解,动态规划90%都是用数组来保存解。根据题目可以知道01背包有二个维度,一个维度是物品,另一个维度是背包重量,所以我们应该定义一个二维数组dp[i][j],dp[i][j]的含义是:从下标为[0-i]的物品⾥任意取,放进容量为j的背包,价值总和最⼤是多少。根据第一可知,要想知道dp[i][j](这个数组中的每个位置都是放的在当前物品树是i,容量是j时的最大值),那就得知道dp[i][j]之前的状态,那怎么从dp[i][j]之前的状态推出dp[i][j]呢,根据定义可知就是我放不放当前第i个物品到背包中去不,那我们就要考虑放进去的到的价值最大,还是不放进去的到的价值最大,当放进去时dp[i-1][j-weight[i]]+value[i],当不放进去时dp[i-1][j],二者取最大的即dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])。根据递推公式可知,i一定要从1开始才行,才能确保递推公式中的i-1大于0,所以我们因该要初始化一下当i为0时,dp[0][j]的值的大小。dp[0][j]代表当只有一个物品时容量为j时,可以得到的最大价值,所以for (int j = 0 ; j < weight[0]; j++) { dp[0][j] = 0; }。接下来看源码分析:
java代码:
//weight[i]:物品i的重量
// value[i]:物品i的价值
// w:背包的容量
public int zeroAndOne(int[] weight,int[] value,int w){
int[][] dp=new int[value.length][w+1];//dp[i][j]:在前i件商品中得到最大容量为j的物品的最大价值。
for(int j=w;j>=weight[0];j--){
dp[0][j]=value[0];//初始化dp[0][j]
}
for(int i=1;i<value.length;i++){//遍历物品
for(int j=1;j<=w;j++){//遍历背包容量
if(weight[i]>j){
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[value.length-1][w];
}
三、完全背包详解
题目:有N件物品和⼀个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件 物品都有⽆限个(也就是可以放⼊背包多次),求解将哪些物品装⼊背包⾥物品价值总和最⼤。
解释:完全背包和01背包问题唯⼀不同的地⽅就是,每种物品有⽆限件。因此他的dp[i][j]的由来就不同了,当放进去时dp[i-1][j-weight[i]]+value[i],当不放进去时dp[i-1][j],二者取最大的即dp[i][j] = Math.max(dp[i - 1][j], dp[i ][j - weight[i]] + value[i])。
代码如下:
java代码:
//weight[i]:物品i的重量
// value[i]:物品i的价值
// w:背包的容量
public int zeroAndOne(int[] weight,int[] value,int w){
int[][] dp=new int[value.length][w+1];//dp[i][j]:在前i件商品中得到最大容量为j的物品的最大价值。
for(int j=w;j>=weight[0];j--){
dp[0][j]=value[0];//初始化dp[0][j]
}
for(int i=1;i<value.length;i++){//遍历物品
for(int j=1;j<=w;j++){//遍历背包容量
if(weight[i]>j){
dp[i][j]=dp[i-1][j];
}else{//注意下面的dp[i]不是dp[i-1]了,因为物品无限个,所以我们可以在dp[i][j之前]的
//位置拿数据了。
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);
}
}
}
return dp[value.length-1][w];
}