一. 分治定界法

分支定界(Branch and bound)：回溯算法的一个改进。贪心拓展空间并修剪劣枝。

贪心 + 遍历 + 剪枝：

  • 一个解由多个顺序子阶段决策构成。
  • 解空间构成一课树。
  • 每个节点中计算定界（上界或下界）值。
  • 从最优定界节点继续拓展求解。
  • 一旦得到一个解，修剪定界值劣于目前解的分治。

二. 0-1背包问题

1.题目描述

Knapsack Problem

2.代码

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
/**
 * 分治定界-求解背包问题
 */
public class Knapsack {

    public static LinkedList<Item> getByBranchBound(double[][] items, double capacity) {
        //1.获取物品的数量
        int n = items.length;

        //2.根据物品的平均价值排序
        LinkedList<Item> itemList = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            //2.1初始化物品
            Item item = new Item(items[i][0], items[i][1]);

            //2.2找到物品该插入的位置
            int k = 0;
            while (k < i && itemList.get(k).unit_value > item.unit_value) {
                k++;
            }

            //2.3插入物品
            itemList.add(k,item);
        }

        //3.生成初始根节点
        int[] best_pack = new int[n];
        double best_value = 0;
        PriorityQueue<NodeInPriorityQueue> queue = new PriorityQueue<>();
        queue.add(
                new NodeInPriorityQueue(
                        0,0,
                        new int[n],
                        0,
                        capacity * itemList.get(0).unit_value
                )
        );
        printPQ(queue);

        //4.循环解决问题
        while (!queue.isEmpty()) {
            // 4.1弹出最大上界结点
            NodeInPriorityQueue node = queue.poll();

            //4.2如果该节点上界大于当前最好情况下的价值
            if (node.upper_bound > best_value) {
                //4.2.1获取当前操作的是第几个item
                int current_item = node.current_item;

                //4.2.2判断是不是叶子节点
                if (current_item == n-1){
                    //刷新最大值
                    if (node.value > best_value) {
                        best_value = node.value;
                        best_pack = node.packedItems.clone();
                    }
                }else {
                    //生成左节点(不放入该item)
                    int[] new_packed_items = new int[n];
                    for (int i = 0; i < current_item; i++) {
                        new_packed_items[i] = node.packedItems[i];
                    }
                    queue.add(
                            new NodeInPriorityQueue(
                                  node.weight,
                                  node.value,
                                  new_packed_items,
                                  current_item+1,
                                  node.value + (capacity-node.weight) * itemList.get(current_item + 1).unit_value
                            )
                    );

                    //生成右节点(放入该item，首先需要判断能不能放得下)
                    if (node.weight + itemList.get(current_item).weight < capacity){
                        new_packed_items = new int[n];
                        for (int i = 0; i < current_item; i++) {
                            new_packed_items[i] = node.packedItems[i];
                        }
                        new_packed_items[current_item] = 1;
                        double new_weight = node.weight + itemList.get(current_item).weight;
                        double new_value = node.value + itemList.get(current_item).value;
                        double new_upper_bound = new_value + (capacity - new_weight) * itemList.get(current_item + 1).unit_value;
                        queue.add(
                                new NodeInPriorityQueue(
                                     new_weight,
                                     new_value,
                                     new_packed_items,
                                     current_item+1,
                                     new_upper_bound
                                )
                        );
                    }
                }

            }

            //4.3打印
            printPQ(queue);
            printBest(best_pack,best_value);
        }

        //5.返回
        LinkedList<Item> packedItems = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (best_pack[i] == 1){
                packedItems.add(itemList.get(i));
            }
        }

        return packedItems;
    }

    /**
     * 打印优先队列
     * @param queue
     */
    private static void printPQ(PriorityQueue<NodeInPriorityQueue> queue) {
        System.out.println("-----------");

        for (NodeInPriorityQueue node : queue) {
            System.out.println(node.weight+" "+node.value+" "+ Arrays.toString(node.packedItems) +" "+node.current_item+" "+node.upper_bound);
        }
    }

    /**
     * 打印当前最好的情况
     * @param best_pack
     * @param best_value
     */
    private static void printBest(int[] best_pack, double best_value) {
        System.out.println("Best:"+ Arrays.toString(best_pack) +" "+best_value);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 物品
 */
public class Item {
    //物品的重量
    double weight;
    //物品的价值
    double value;
    //物品的平均价值
    double unit_value;

    public Item(double weight, double value){
        this.weight = weight;
        this.value = value;
        this.unit_value = value/weight;
    }
}
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
/**
 * 节点
 */
public class NodeInPriorityQueue implements Comparable<NodeInPriorityQueue> {
    //当前的重量
    double weight;
    //当前的价值
    double value;
    //当前放入背包的item
    int[] packedItems;
    //当前的item
    int current_item;
    //该节点的上界
    double upper_bound;

    public NodeInPriorityQueue(double weight, double value, int[] packedItems,
                               int current_item, double upper_bound) {
        this.weight = weight;
        this.value = value;
        this.packedItems = packedItems;
        this.current_item = current_item;
        this.upper_bound = upper_bound;
    }

    @Override
    public int compareTo(NodeInPriorityQueue o) {
        if(this.upper_bound - o.upper_bound > 0) return -1;
        else if(this.upper_bound - o.upper_bound < 0) return 1;
        else return 0;
    }
}
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
/**
 * 测试
 */
public class KnapsackTest {
    public static void main(String[] args) {
        double[][] items = {{7,42},{5,25},{3,12},{4,40}};
        double capacity = 10;
        LinkedList<Item> packedItems = Knapsack.getByBranchBound(items, capacity);
        int packedValue = 0;
        String packedItemsStr = "";
        for(Item item : packedItems) {
            packedValue += item.value;
            packedItemsStr = packedItemsStr + "weight " + item.weight + ", value " + item.value + "; ";
        }
        System.out.println("packed items: " + packedItemsStr);
        System.out.println("packed value: " + packedValue);
    }

}

//运行结果
-----------
0.0 0.0 [0, 0, 0, 0] 0 100.0
-----------
4.0 40.0 [1, 0, 0, 0] 1 76.0
0.0 0.0 [0, 0, 0, 0] 1 60.0
Best:[0, 0, 0, 0] 0.0
-----------
4.0 40.0 [1, 0, 0, 0] 2 70.0
0.0 0.0 [0, 0, 0, 0] 1 60.0
Best:[0, 0, 0, 0] 0.0
-----------
9.0 65.0 [1, 0, 1, 0] 3 69.0
0.0 0.0 [0, 0, 0, 0] 1 60.0
4.0 40.0 [1, 0, 0, 0] 3 64.0
Best:[0, 0, 0, 0] 0.0
-----------
4.0 40.0 [1, 0, 0, 0] 3 64.0
0.0 0.0 [0, 0, 0, 0] 1 60.0
Best:[1, 0, 1, 0] 65.0
-----------
0.0 0.0 [0, 0, 0, 0] 1 60.0
Best:[1, 0, 1, 0] 65.0
-----------
Best:[1, 0, 1, 0] 65.0
packed items: weight 4.0, value 40.0; weight 5.0, value 25.0; 
packed value: 65

三. 指派问题

1.题目描述

2.代码

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
/**
 * 分治定界-求解指派问题
 */
public class Assignment {

    public static int[] get(int[][] cost_matrix) {
        //记录有多少个人可以安排
        int n = cost_matrix.length;

        //记录最佳安排和最少的花费
        int[] best_assignment = new int[n];
        int min_cost = Integer.MAX_VALUE;

        //当前安排的人
        int current_person = 0;

        //记录安排情况和花费
        int[] assignment = new int[n];
        int cost = 0;

        //记录工作的安排情况，-1表示没有安排
        int[] job_flag = new int[n];
        for (int i = 0; i < n; i++) {
            job_flag[i] = -1;
        }

        //计算最小的花费
        int lower_bound = get_lower_bound(assignment,job_flag,current_person-1,cost,cost_matrix);

        //生成初始根节点
        PriorityQueue<NodeInPriorityQueue> queue = new PriorityQueue<>();
        queue.add(
                new NodeInPriorityQueue(
                        assignment,
                        current_person,
                        cost,
                        job_flag,
                        lower_bound
                )
        );
        printPQ(queue);

        //循环得到结果
        while (!queue.isEmpty()){
            //弹出最小上界节点
            NodeInPriorityQueue node = queue.poll();

            //如果该节点下界小于当前最好情况下的花费
            if (node.lower_bound < min_cost) {
                //获取当前操作的是第几个person
                current_person = node.current_person;

                //判断是不是叶子节点
                if (current_person == n-1){
                    //刷新工作安排的情况
                    for (int j = 0; j < n; j++) {
                        //刷新
                        if (node.job_flag[j] == -1){
                            node.assignment[current_person] = j;
                            node.cost += cost_matrix[current_person][j];
                        }
                    }

                    //刷新最小的花费
                    if (node.cost < min_cost){
                        min_cost = node.cost;
                        best_assignment = node.assignment.clone();
                    }
                }else {
                    //工作依次安排
                    for (int i = 0; i < n; i++) {
                        if (node.job_flag[i] == -1){
                            //计算人员安排情况
                            assignment = node.assignment.clone();
                            assignment[current_person] = i;

                            //计算工作安排情况
                            job_flag = node.job_flag.clone();
                            job_flag[i] = current_person;

                            //计算花费
                            cost = node.cost + cost_matrix[current_person][i];

                            //计算下界
                            lower_bound = get_lower_bound(assignment, job_flag,current_person,cost,cost_matrix);

                            //添加节点
                            queue.add(
                                    new NodeInPriorityQueue(
                                        assignment,
                                        current_person+1,
                                        cost,
                                        job_flag,
                                        lower_bound
                                    )
                            );
                        }
                    }
                }
            }

            printPQ(queue);
            printBest(best_assignment,min_cost);
        }

        return best_assignment;
    }

    /**
     * 计算节点下界
     * @param assignment
     * @param job_flag
     * @param current_person
     * @param cost
     * @param cost_matrix
     * @return
     */
    private static int get_lower_bound(int[] assignment, int[] job_flag, int current_person, int cost, int[][] cost_matrix) {
        //获取person的数量
        int n = cost_matrix.length;

        //下界的初值(当前确定的)
        int lower_bound = cost;

        //计算下界(计算当前person之后的)
        for (int i = current_person+1; i < n; i++){
            int temp = cost_matrix[i][0];

            for (int j = 1; j < n; j++) {
                if (job_flag[j] == -1){
                    if (cost_matrix[i][j] < temp){
                        temp = cost_matrix[i][j];
                    }
                }
            }

            lower_bound = lower_bound + temp;
        }

        return lower_bound;
    }

    /**
     * 打印优先队列
     * @param queue
     */
    private static void printPQ(PriorityQueue<NodeInPriorityQueue> queue) {
        System.out.println("-----------");

        for (NodeInPriorityQueue node : queue) {
            System.out.println(node);
        }
    }

    /**
     * 打印当前最好的情况
     * @param best_pack
     * @param min_cost
     */
    private static void printBest(int[] best_pack, double min_cost) {
        System.out.println("Best:"+ Arrays.toString(best_pack) +" "+min_cost);
    }
}
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
/**
 * 节点
 */
public class NodeInPriorityQueue implements Comparable<NodeInPriorityQueue> {
    //人员安排情况
    int[] assignment;
    //当前的人
    int current_person;
    //当前的花费
    int cost;
    //工作的安排情况
    int[] job_flag;
    //下界
    int lower_bound;

    public NodeInPriorityQueue(int[] assignment, int current_person,
                               int cost, int[] job_flag, int lower_bound) {
        this.assignment = assignment;
        this.current_person = current_person;
        this.cost = cost;
        this.job_flag = job_flag;
        this.lower_bound = lower_bound;
    }

    @Override
    public int compareTo(NodeInPriorityQueue o) {
        if(this.lower_bound - o.lower_bound > 0) return 1;
        else if(this.lower_bound - o.lower_bound < 0) return -1;
        else return 0;
    }

    @Override
    public String toString() {
        return current_person +
                " " + cost +
                " " + lower_bound +
                " " + Arrays.toString(assignment) +
                " " + Arrays.toString(job_flag);
    }
}
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
71
72
73
/**
 * 测试
 */
public class AssignmentTest {
    public static void main(String[] args) {
        int[][] cost = {{9,2,7,8},{6,4,3,7},{5,8,1,8},{7,6,9,4}};
        Assignment.get(cost);
    }
}

//运行结果
-----------
0 0 10 [0, 0, 0, 0] [-1, -1, -1, -1]
-----------
1 2 10 [1, 0, 0, 0] [-1, 0, -1, -1]
1 9 17 [0, 0, 0, 0] [0, -1, -1, -1]
1 7 20 [2, 0, 0, 0] [-1, -1, 0, -1]
1 8 18 [3, 0, 0, 0] [-1, -1, -1, 0]
Best:[0, 0, 0, 0] 2.147483647E9
-----------
2 8 13 [1, 0, 0, 0] [1, 0, -1, -1]
2 5 14 [1, 2, 0, 0] [-1, 0, 1, -1]
2 9 17 [1, 3, 0, 0] [-1, 0, -1, 1]
1 8 18 [3, 0, 0, 0] [-1, -1, -1, 0]
1 9 17 [0, 0, 0, 0] [0, -1, -1, -1]
1 7 20 [2, 0, 0, 0] [-1, -1, 0, -1]
Best:[0, 0, 0, 0] 2.147483647E9
-----------
3 9 13 [1, 0, 2, 0] [1, 0, 2, -1]
1 9 17 [0, 0, 0, 0] [0, -1, -1, -1]
2 5 14 [1, 2, 0, 0] [-1, 0, 1, -1]
1 8 18 [3, 0, 0, 0] [-1, -1, -1, 0]
1 7 20 [2, 0, 0, 0] [-1, -1, 0, -1]
2 9 17 [1, 3, 0, 0] [-1, 0, -1, 1]
3 16 23 [1, 0, 3, 0] [1, 0, -1, 2]
Best:[0, 0, 0, 0] 2.147483647E9
-----------
2 5 14 [1, 2, 0, 0] [-1, 0, 1, -1]
1 9 17 [0, 0, 0, 0] [0, -1, -1, -1]
2 9 17 [1, 3, 0, 0] [-1, 0, -1, 1]
1 8 18 [3, 0, 0, 0] [-1, -1, -1, 0]
1 7 20 [2, 0, 0, 0] [-1, -1, 0, -1]
3 16 23 [1, 0, 3, 0] [1, 0, -1, 2]
Best:[1, 0, 2, 3] 13.0
-----------
1 9 17 [0, 0, 0, 0] [0, -1, -1, -1]
1 8 18 [3, 0, 0, 0] [-1, -1, -1, 0]
2 9 17 [1, 3, 0, 0] [-1, 0, -1, 1]
3 16 23 [1, 0, 3, 0] [1, 0, -1, 2]
1 7 20 [2, 0, 0, 0] [-1, -1, 0, -1]
Best:[1, 0, 2, 3] 13.0
-----------
2 9 17 [1, 3, 0, 0] [-1, 0, -1, 1]
1 8 18 [3, 0, 0, 0] [-1, -1, -1, 0]
1 7 20 [2, 0, 0, 0] [-1, -1, 0, -1]
3 16 23 [1, 0, 3, 0] [1, 0, -1, 2]
Best:[1, 0, 2, 3] 13.0
-----------
1 8 18 [3, 0, 0, 0] [-1, -1, -1, 0]
3 16 23 [1, 0, 3, 0] [1, 0, -1, 2]
1 7 20 [2, 0, 0, 0] [-1, -1, 0, -1]
Best:[1, 0, 2, 3] 13.0
-----------
1 7 20 [2, 0, 0, 0] [-1, -1, 0, -1]
3 16 23 [1, 0, 3, 0] [1, 0, -1, 2]
Best:[1, 0, 2, 3] 13.0
-----------
3 16 23 [1, 0, 3, 0] [1, 0, -1, 2]
Best:[1, 0, 2, 3] 13.0
-----------
Best:[1, 0, 2, 3] 13.0

Process finished with exit code 0