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%