0-1背包问题(回溯法)

0-1背包

有一个背包,背包的总承载重量是Wkg,现在有n个物品,每个物品的重量不等,并且不可分割。我们期望选择几件物品,装载到背包中。在不超过背包所能装载重量的前提下,如何让背包中物品的总重量最大?

0-1背包问题的回溯实现技巧:
第 13 行的递归调用表示不选择当前物品,直接考虑下一个(第 i+1 个),故 cw 不更新

第 15 行的递归调用表示选择了当前物品,故考虑下一个时,cw 通过入参更新为 cw + items[i]

函数入口处的 if 分支表明递归结束条件,并保证 maxW 跟踪所有选择中的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class PkgDemo {

public int maxW = Integer.MIN_VALUE; // 存储背包中物品总重量的最大值
// cw 表示当前已经装进去的物品的重量和;i 表示考察到哪个物品了;
// w 背包重量;items 表示每个物品的重量;n 表示物品个数
// 假设背包可承受重量 100,物品个数 10,物品重量存储在数组 a 中,那可以这样调用函数:
// f(0, 0, a, 10, 100)
public void f(int i, int cw, int[] items, int n, int w) {
if (cw == w || i == n) { // cw==w 表示装满了 ;i==n 表示已经考察完所有的物品
if (cw > maxW) maxW = cw;
return;
}
f(i + 1, cw, items, n, w); //当前物品不装进背包
if (cw + items[i] <= w) { // 已经超过可以背包承受的重量的时候,就不要再装了
f(i + 1, cw + items[i], items, n, w); //当前物品装进背包
}
}
}

Java代码

0-1背包最大重量问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package com.ludepeng.datastruct.algorithm.backtrackingAlgorithm.packageZeroOne;

/**
* @description: 使用回溯的思想来解决0-1背包的问题
*
* <p>解决的主要思路是通过回溯
*
* <p>重点,对于每个物品来说,有装入背包与不装入背包两种选择,也就是需要考察每个有加入背包的情况与不加入的情况
* @author: rhsphere
* @since: 2019-11-04 15:45 by jdk 1.8
*/
public class Package {
/** 背包中物品总重量的最大值 */
public int maxW = Integer.MIN_VALUE;

/**
* 计算最大放入的信息
*
* <p>1,物品不能分隔
*
* <p>2,在包中放入的数量不能超过maxNum
*
* <p>3,包装的总重量不能超过maxWeight
*
* @param index 当前物品索引
* @param sum 当前的总重量
* @param items 物品
* @param maxNum 最大的数物品的个数
* @param maxWeight
*/
public void countMaxPkg(int index, int sum, int[] items, int maxNum, int maxWeight) {
// 1. 如果当前重量到达最大总重量,或者数量达到最达限制,则设置当前最大值
if (index == maxNum || sum == maxWeight) {
// 检查当前是否已经超过了总上一个值
if (maxW < sum) {
maxW = sum;
}

return;
}

//当前物品不装进背包里面
countMaxPkg(index + 1, sum, items, maxNum, maxWeight);

// 如果当前还未超过最大值,则继续循环
if (sum + items[index] <= maxWeight) {
countMaxPkg(index + 1, sum + items[index], items, maxNum, maxWeight); //当前物品装到背包里面
}
}
}

0-1背包最大价值问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package com.ludepeng.datastruct.algorithm.backtrackingAlgorithm.packageZeroOne;

/**
* 使用回溯的思想来解决0-1背包的问题
*
* <p>每个物品的重量不同,价值也不相同,在重量不超过背包重量的前提下,让背包的总价值最大化
*
* <p>解决的主要思路是通过回溯
*
* <p>重点,对于每个物品来说,有装入背包与不装入背包两种选择,也就是需要考察每个有加入背包的情况与不加入的情况
* @description:
* @author: rhsphere
* @since: 2019-11-04 16:09 by jdk 1.8
*/
public class PackageValue {
/** 背包中物品总重量的最大值 */
public int maxValue = Integer.MIN_VALUE;

/** 当前背包的最大总重量 */
public int sumMaxWeight = Integer.MIN_VALUE;

/**
* 计算最大放入的信息
*
* <p>1,物品不能分隔
*
* <p>2,在包中放入的数量不能超过maxNum
*
* <p>3,包装的总重量不能超过maxWeight
*
* @param index 当前物品索引
* @param sumValue 当前的总重量
* @param items 物品
* @param maxNum 最大的数物品的个数
* @param maxWeight
*/
public void countMaxPkg(
int index, int sumValue, int sumWeight, PkgValue[] items, int maxNum, int maxWeight) {

// 1,如果当前重量到达最大总重量,或者数量达到最达限制,则设置当前最大值
if (index == maxNum || sumWeight == maxWeight) {
// 检查总重量是否更重
if (sumMaxWeight < sumWeight) {
sumMaxWeight = sumWeight;
}
// 检查当前价值是否更大
if (maxValue < sumValue) {
maxValue = sumValue;
}

return;
}

// 针对每个物品,有当前不加入背包中计算价值
countMaxPkg(index + 1, sumValue, sumWeight, items, maxNum, maxWeight);

// 当前的最大总重量还是要小于限制值
if (sumWeight + items[index].getWeight() <= maxWeight) {

// 针对每个物品,有当前加入背包计算价值
countMaxPkg(
index + 1,
sumValue + items[index].getValue(),
sumWeight + items[index].getWeight(),
items,
maxNum,
maxWeight);
}
}
}

0%