背包问题/01背包
背包问题
泛指一类「给定价值与成本」，同时「限定决策规则」，在这样的条件下，如何实现价值最大化的问题【1】
01背包
「01背包」是指给定物品价值与体积（对应了「给定价值与成本」），在规定容量下（对应了「限定决策规则」）如何使得所选物品的总价值最大【1】
01背包的题目：
经典01背包
给定两个长度都为N的数组weights和values,
weights[i]和values[i]分别代表i号物品的重量和价值。
给定一个正数bag，表示1个载重bag的袋子,
你装的物品不能超过这个重量。
返回你能装下最多的价值是多少?
经典01背包暴力解决方法
/**
* 只剩下了rest的空间
* index..... 的货物自由选择，但是剩下的空间rest 不要小于 0
* 返回 能够获得的最大价值
*
* @param w
* @param v
* @param index
* @param rest
* @return
*/
public static int process2( int[] w, int[] v, int index, int rest ) {
// 认为此时没有方案
if ( rest <= 0 ) {
return 0;
}
// 重量没超 且此时存在 rest>=0
if ( index == w.length ) {
return 0;
}
// 没有选当前物品
int p1 = process2( w, v, index + 1, rest );
// 选择了当前位置的物品
int p2 = Integer.MIN_VALUE;
// 如果选择了当前位置的物品，且最后有合理的方案
if ( rest >= w[index] ) {
p2 = v[index] + process2( w, v, index + 1, rest - w[index] );
}
return Math.max( p1, p2 );
}
//物品有3件
static int N = 3;
//背包容量为5
static int W = 5;
static int weight[] = { 1, 2, 3 };
static int value[] = { 6, 9, 13 };
public static void main( String[] args ) {
System.out.println( process2( weight, value, 0, W ) );
}
递归改动态规划
public static int dpWay( int[] w, int[] v, int bag ) {
int N = w.length;
int[][] dp = new int[N + 1][bag + 1];
// dp[N][...] = 0
for ( int index = N - 1; index >= 0; index-- ) {
// rest < 0
for ( int rest = 0; rest <= bag; rest++ ) {
int p1 = dp[index + 1][rest];
int p2 = -1;
if ( rest - w[index] >= 0 ) {
p2 = v[index] + dp[index + 1][rest - w[index]];
}
dp[index][rest] = Math.max( p1, p2 );
// int p1 = process2( w, v, index + 1, rest );
// int p2 = Integer.MIN_VALUE;
// if ( rest >= w[index] ) {
// p2 = v[index] + process2( w, v, index + 1, rest - w[index] );
// }
// return Math.max( p1, p2 );
}
}
for ( int i = 0; i < dp.length; i++ ) {
for ( int j = 0; j < dp[0].length; j++ ) {
System.out.printf( "%3d", dp[i][j] );
}
System.out.println();
}
return dp[0][bag];
}
输出
暴力递归改为动态规划
0 6 9 15 19 22
0 0 9 13 13 22
0 0 0 13 13 13
0 0 0 0 0 0
22
01背包一般解法
定义二维数组dp[][]
[ i ] [ j ] 来表示前 i件物品装入容量为j的背包所能得到的最大价值
对于dp[ i ] [ j ]来说，i指的是前i件物品，j指的是用了多少背包空间
于是对于dp[ i ] [ j ]来说，有公式 （图源水印处）
dp 状态表示 f(i,j)
集合: 所有只考虑前i个物品,且总体积不超过j的选法的集合
属性: max
状态计算
f(i,j)
所有不选第 i 个物品的方案
1---(i-1) <= j
f(i-1,j)
所有选了第 i 个物品的方案
因为第 i 个物品的价值固定, wi 已经固定,
1---v (i-1) <= j-v(i)
f(i-1,j-v(i) ) + w(i)
(不重复,不遗漏)
所有物品都只有两种情况,选 或者 不选
选它
对于第 i 件物品, 如果把它放入背包能使目前容量下的背包价值最大,
则
dp[ i ] [ j ] = dp[ i-1 ] [ j -w ] + v
即 当前的这个 i , j 所对应位置的最大价值为
将 i-1 件物品 装入 j -w 大小的背包所取得的最大值 // dp[ i-1 ] [ j -w ]
加上 // +
当前物品的价值 // v
(也就是上10楼的最快时间 = 上到第9 楼的最快时间+上第十楼的时间)
不选它
就不把第i件物品放入背包，
dp [ i ] [ j ] = dp [ i -1 ] [ j ]
即前i件物品放入容量为j的背包中所得到的最大值为
i - 1 件物品放入 容量为j 的背包中所得到的最大值
(当前物品太大了,放不进去,所以最大价值的选择方法就是 前i-1件物品中能得到最大价值的选择方法)
模拟过程
现在有三件物品，这些物品的价值和所占容量如表所示，有一个容量为5的背包，在装满背包的情况下，如何使得背包里的价值最大？
| i | 1 | 2 | 3 |
|---|---|---|---|
| w (重量) | 1 | 2 | 3 |
| v (价值) | 6 | 9 | 13 |
先来用二维数组模仿一下数组内部情况
-
当 i=0 ,即一件商品都不选,价值为0,
当 j =0,即背包容量为0,则无法装入,价值也为0
i/j 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0
2 0
3 0
- 当i=1…3,j=1…5 选
i件商品放入容量为j的背包
背包总重量为 5
| w (重量) | 1 | 2 | 3 |
| v (价值) | 6 | 9 | 13 |
i/j 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 6 6 6 6 6
2 0 6
3 0 6
比如 dp[1] [3] = max (dp[0] [3],dp[0] [2] +6)
当只有一件物品放入容量为3 的背包时,
要么选择不放入 ,即 dp[i][j] = dp[i-1][j]
如果选择放入,即 dp [i] [j] = dp[i-1] [j-w] + v
- 当i=2…3,j=3…5 选
i件商品放入容量为j的背包
背包总重量为 5
| w (重量) | 1 | 2 | 3 |
| v (价值) | 6 | 9 | 13 |
i/j 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 6 6 6 6 6
2 0 6 9 15 15 15
3 0 6 9 15 19 22
状态方程 :dp[ i ] [ j ] = ( dp [ i -1 ] [ j ] , dp[ i-1 ] [ j -w ] + v )
比如 dp[2] [2] = max(dp[2-1] [2] , dp[2-1] [2-2] +9 )
=max (6,9)=9
dp[3] [4] =max (dp [3-1] [4] , dp[3-1] [4-3] + 13 )
=max(15 ,6+13) = 19
代码实现
static int N = 3;//物品有3件
static int W = 5;//背包容量为5
static int weight[] = { 1, 2, 3 };
static int value[] = { 6, 9, 13 };
public static void getValue() {
//sum[i][j]意思是：背包容量为j时，在前i件物品中取小于等于i件物品，此时取得的物品的价值最大
int sum[][] = new int[N + 1][W + 1];
for ( int i = 1; i <= N; i++ ) {
for ( int j = 1; j <= W; j++ ) {
if ( weight[i-1] > j ) {
//太重了，拿不了
// 不拿： sum[i-1][j]
sum[i][j] = sum[i - 1][j];
} else {
//拿：sum[i-1][j-weight[i-1]]+value[i-1]
//sum[i-1][j-weight[i-1]]可以理解为此时还没拿第i件的最大价值，要留weight[i]空间
sum[i][j] = Math.max( sum[i - 1][j], sum[i - 1][j - weight[i-1]] + value[i-1] );
}
}
}
for ( int i = 0; i < N + 1; i++ ) {
for ( int j = 0; j < W + 1; j++ ) {
System.out.print( " " + sum[i][j] );
}
System.out.println();
}
//System.out.println( sum[2][4] );
}
public static void main( String[] args ) {
getValue();
}
时间和空间都是 n^2
优化
状态转移方程为 max( dp [i - 1] [j] , dp [i - 1] [j - w] + v);
dp[i] [j] 只依赖于dp[i-1] [j]
可以用一维数组来存放最大价值
方程简化为
dp[j] = max(dp[j],dp[j-w]+v)
public static void getValue1() {
int sum[]= new int[W];
for(int i=1;i<N;i++) {
// 注意是 从w递减到 1
for(int j=W-1;j>=1;j--) {
if(weight[i]<=j) {
sum[j]=Math.max(sum[j], sum[j-weight[i]]+value[i]);
}
}
}
System.out.println(sum[w-1]);
}
为什么优化为一维数组时,要从后往前遍历?
原状态方程:
dp[ i ] [ j ] = ( dp [ i -1 ] [ j ] , dp[ i-1 ] [ j -w ] + v )
优化后的方程:
dp[j] = max(dp[j],dp[j-w]+v)
对于 dp[ i ] [ j ] = dp [ i -1 ] [ j ] 它等价于dp [j] = dp[j]
因为dp[ i ] [ j ] 是从i-1 即上一行 的状态 计算得来的
计算dp[ i ] [ j ] 时, dp [ i -1 ] [ j ] 记录的就是还没有被更新过的值
重点在于 dp[ i-1 ] [ j -w ] + v 是否等于 dp[j-w]+v
即 dp[i-1] [j-w ] 是否等价于dp [j-w]
dp[j-w] 需要代表 dp[i-1] [j-w]
当正序遍历时, j 从1 到w
而 j-w 一定小于 j
j-w 处的会被逐渐更新
而 我们后面还需要 用到的 j-w 的值已经先被更新,
状态方程变成了dp[ i ] [ j ] = dp[ i ] [ j -w ] + v (即当前这一层的 j-w ,而我们需要的是 上一层的 j-w )
所以会出现bug
而倒叙遍历时
j-w 处的值还是原来的值,不会受到影响,
保证了 dp[ i-1 ] [ j -w ] + v 等价于 dp[j-w]+v
所以选用倒叙遍历
public static void getValue1() {
int sum[] = new int[W];
for ( int i = 1; i <= N; i++ ) {
for ( int j = W; j >= w[i]; j-- ) {
sum[j] = max( sum[j], sum[j - w[i]] + v[i] );
}
}
System.out.println(sum[w-1]);
}
一纬数组优化错误示范
public static void getValueWrongWay() {
int sum[] = new int[W+1];
for ( int i = 0; i <N; i++ ) {
for ( int j = weight[i]; j <= W ; j++ ) {
sum[j] = Math.max( sum[j], sum[j - weight[i]] + value[i] );
System.out.println("此时i="+ i + " j=" + j + " 整个数组情况为：" + Arrays.toString( sum ) );
}
}
System.out.println(sum[W]);
}
输出：
一纬数组优化错误示范
此时i=0 j=1 整个数组情况为：[0, 6, 0, 0, 0, 0]
此时i=0 j=2 整个数组情况为：[0, 6, 12, 0, 0, 0]
此时i=0 j=3 整个数组情况为：[0, 6, 12, 18, 0, 0]
此时i=0 j=4 整个数组情况为：[0, 6, 12, 18, 24, 0]
此时i=0 j=5 整个数组情况为：[0, 6, 12, 18, 24, 30]
（因为 i=0 是不变的，相当于每次都是拿第一件物品加上前一个位置）
此时i=1 j=2 整个数组情况为：[0, 6, 12, 18, 24, 30]
此时i=1 j=3 整个数组情况为：[0, 6, 12, 18, 24, 30]
此时i=1 j=4 整个数组情况为：[0, 6, 12, 18, 24, 30]
此时i=1 j=5 整个数组情况为：[0, 6, 12, 18, 24, 30]
此时i=2 j=3 整个数组情况为：[0, 6, 12, 18, 24, 30]
此时i=2 j=4 整个数组情况为：[0, 6, 12, 18, 24, 30]
此时i=2 j=5 整个数组情况为：[0, 6, 12, 18, 24, 30]
30
正确🌰
public static void getValue1() {
int sum[] = new int[W+1];
for ( int i = 0; i <N; i++ ) {
for ( int j = W; j >= weight[i]; j-- ) {
sum[j] = Math.max( sum[j], sum[j - weight[i]] + value[i] );
System.out.println("此时i="+ i + " j=" + j + " 整个数组情况为：" + Arrays.toString( sum ) );
}
}
System.out.println(sum[W]);
}
输出
一纬数组优化
此时i=0 j=5 整个数组情况为：[0, 0, 0, 0, 0, 6]
此时i=0 j=4 整个数组情况为：[0, 0, 0, 0, 6, 6]
此时i=0 j=3 整个数组情况为：[0, 0, 0, 6, 6, 6]
此时i=0 j=2 整个数组情况为：[0, 0, 6, 6, 6, 6]
此时i=0 j=1 整个数组情况为：[0, 6, 6, 6, 6, 6]
（从最后一个开始，而我们的方程是依赖前一个数字，所以不会造成影响）
此时i=1 j=5 整个数组情况为：[0, 6, 6, 6, 6, 15]
此时i=1 j=4 整个数组情况为：[0, 6, 6, 6, 15, 15]
此时i=1 j=3 整个数组情况为：[0, 6, 6, 15, 15, 15]
此时i=1 j=2 整个数组情况为：[0, 6, 9, 15, 15, 15]
此时i=2 j=5 整个数组情况为：[0, 6, 9, 15, 15, 22]
此时i=2 j=4 整个数组情况为：[0, 6, 9, 15, 19, 22]
此时i=2 j=3 整个数组情况为：[0, 6, 9, 15, 19, 22]
22
【1】https://mp.weixin.qq.com/s/xmgK7SrTnFIM3Owpk-emmg
【2】https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/ti-gong-wo-de-yi-ge-xie-dong-tai-gui-hua-44n4/