Algo | 带容量的设备选址问题

本文为《算法》课程上的作业,研究和实现容量设备选址问题求解的几个解决方案。本文涉及到了贪心法、局部搜索、模拟退火。

[GitHub] [测试样例] [测试结果]

Description

带容量的设备选址问题(CFLP)是一个求解最优解问题,属于NP类问题。由于解的可能非常多,不可能一一枚举,在给定的有限时间内,只能求出接近最优解的解。

带容量的设备选址问题给定了数量$n$个设备和$m​$个人,其中每个设备都有开设的费用和容纳容量两个属性,而每个人有需求、到每一个设备的费用两个属性。设备可以选择开或者不开,但是每个人必须都有所对应的设备,并且设备要满足人的需求。

假设有10个设备和50个人,那么就一共有$50^{10}$种解,每个人都可以选择其中一个设备。除去大部分非法的解(即不满足容量限制),剩下的解的数量也是非常庞大的。CFLP问题就是在这些合法的解中找到最优解,但是所需要的时间是非常长的。因此我们退而求其次,找到一个看起来比较接近最优解的解即可。

求解设备选址问题,通常采用启发式搜索,即我们选择一个初始解,按一定的策略进行启发式搜索,让我们所搜索到的解越来越接近最优解。启发式搜索的关键在于,如何定义搜索的策略。启发式搜索最终求得的解一定程度受初始解和搜索的策略的影响。当然,贪心法也可以求解CFLP问题,但是贪心法的关键在于如何定义贪心的策略。贪心法的解受贪心策略的影响,因此在策略固定的时候,贪心法的解是固定不变的。

接下来,我们首先设计好程序的数据结构、输入处理、输出处理。

Structure

Types

按照CFLP的内容,我们需要定义设备类型、消费者类型、解类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Facility {
int capacity;
int openingCost;
};

struct Customer {
int demand;
std::vector<int> assignmentCost;
};

struct Result {
int cost;
std::vector<bool> status;
std::vector<size_t> assignment;
};

其中,解类型包含了一切我们需要输出的数据。不过,为了防止数据错误,我们应该编写一个验证解类型的正确性的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool check(const std::vector<Facility> &f, const std::vector<Customer> &c, const Result res) {
int cost = 0, capacity[f.size()] = {0};
for (size_t i = 0; i < f.size(); i++) {
if (res.status[i]) {
cost += f[i].openingCost;
}
}
for (size_t i = 0; i < c.size(); i++) {
capacity[res.assignment[i]] += c[i].demand;
if (capacity[res.assignment[i]] > f[res.assignment[i]].capacity) {
return false;
}
cost += c[i].assignmentCost[res.assignment[i]];
}
return cost == res.cost;
}

在任意一种方法求解到解之后,都可以使用check函数来验证解的合法性。

Input

在CFLP中,我们需要处理的输入有两类:一个是CFLP的数据输入,一个是CFLP的当前最优解输入。

前者是CFLP的数据来源,而后者是CFLP的解。每次求得CFLP的解,都与当前最优解对比,如果CFLP的解比当前最优解更加好,那么就将我们求得的解存储到本地中,以提供给下一次求CFLP解进行对比。因为设备选址问题的启发式策略可能是随机的,将当前最优解存储下来有利于数据的对比。

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
std::pair<Result, std::pair<std::vector<Facility>, std::vector<Customer>>> input(int testcase) {
size_t facilityNum, customerNum;
std::vector<Facility> facilities;
std::vector<Customer> customers;
Result result;
// 数据输入
std::ifstream in("testcases/p" + std::to_string(testcase));
in >> facilityNum >> customerNum;
for (size_t i = 0; i < facilityNum; i++) {
Facility facility;
in >> facility.capacity >> facility.openingCost;
facilities.push_back(facility);
}
for (size_t i = 0; i < customerNum; i++) {
Customer customer;
double val;
in >> val;
customer.demand = (int) val;
customers.push_back(customer);
}
for (size_t i = 0; i < facilityNum; i++) {
for (size_t j = 0; j < customerNum; j++) {
double val;
in >> val;
customers[j].assignmentCost.push_back((int) val);
}
}
in.close();
// 当前最优解输入
std::ifstream rin("best/p" + std::to_string(testcase));
if (rin.is_open()) {
rin >> result.cost;
for (size_t i = 0; i < facilityNum; i++) {
bool val;
rin >> val;
result.status.push_back(val);
}
for (size_t i = 0; i < customerNum; i++) {
size_t val;
rin >> val;
result.assignment.push_back(val);
}
} else {
result.cost = 0;
}
rin.close();
return std::make_pair(result, std::make_pair(facilities, customers));
}

Output

与输入一样,输出也需要处理两类数据,一个是将求得的解输出到控制台中,另一个是将求得的解和当前最优解对比,如果当前最优解不够好,那么就更新本地存储的当前最优解。

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
void output(int testcase, Result best, Result res) {
// 解输出
std::cout << res.cost << std::endl;
if (res.status.size() != 0) {
std::cout << res.status[0];
for (size_t i = 1; i < res.status.size(); i++) {
std::cout << ' ' << res.status[i];
}
std::cout << std::endl;
}
if (res.assignment.size() != 0) {
std::cout << res.assignment[0];
for (size_t i = 1; i < res.assignment.size(); i++) {
std::cout << ' ' << res.assignment[i];
}
std::cout << std::endl;
}
// 对比、存储当前最优解
if (best.cost < res.cost && best.cost != 0) {
std::cout << "Compare with best cost " << best.cost << ", percentage " << (float)(res.cost - best.cost) / best.cost * 100 << '%' << std::endl;
} else {
std::cout << "Get the best cost" << std::endl;
std::ofstream out("best/p" + std::to_string(testcase));
out << res.cost << std::endl;
if (res.status.size() != 0) {
out << res.status[0];
for (size_t i = 1; i < res.status.size(); i++) {
out << ' ' << res.status[i];
}
out << std::endl;
}
if (res.assignment.size() != 0) {
out << res.assignment[0];
for (size_t i = 1; i < res.assignment.size(); i++) {
out << ' ' << res.assignment[i];
}
out << std::endl;
}
out.close();
}
}

当然,我们还需要记录一下程序执行的时间,以完成我们的数据记录表。

1
2
3
4
5
6
7
8
9
10
11
12
void test(int testcase, std::function<Result(std::vector<Facility>, std::vector<Customer>)> fn) {
std::cout << "Test " << testcase << ":" << std::endl;
std::pair<Result, std::pair<std::vector<Facility>, std::vector<Customer>>> data = input(testcase);
auto start = std::chrono::system_clock::now();
Result res = fn(data.second.first, data.second.second);
auto stop = std::chrono::system_clock::now();
output(testcase, data.first, res);
std::ofstream out("best/markdown", std::ios_base::app);
out << "| p" << testcase << " | " << res.cost << " | " << (double) std::chrono::duration_cast<std::chrono::milliseconds>(stop - start).count() / 1000 << " |" << std::endl;
out.close();
std::cout << std::endl;
}

Approach #1 Greedy

Intuition

贪心法是解决设备选址问题的其中一种方法,应该也算是最简单的方法了(除了随机法)。但是贪心法求得的解很大程度取决于贪心策略,通常和最优解有蛮大程度的差距。

贪心法的核心在于如何制定贪心策略,一个贪心策略的好坏决定了解的好坏。而且,贪心法通常只能考虑到一般情况,如果有特殊测试样例,可能贪心法还不如随机法。

我们知道,设备可以选择开与不开,而人必须要选择一个设备。因此,最简单的贪心策略就是让人去选择最优的设备。为了让程序更简单,我们可以按输入数据的人的顺序来选择设备。

$Solution = \Sigma Facility.openingCost + \Sigma Min(Customer.assignmentCost)$

当然,我们要加一下限制,必须让解合法,也就是将人的安排费用从小到大排序,优先选择费用小的并且容量足够的设备。

不过,如果你实现了这种策略之后,就会发现,基本所有设备都被开启了。这样会产生大量的费用,因为某些人即使选择比最小费用差一点的设备,而使得设备空闲下来,可能总费用比选择最小费用的设备还要低。为了减弱这种情况对解的影响,我们将设备所使用的容量排序,每次删去已使用容量最少的设备,然后再重新按之前的策略进行设备分配。

如果删去了某个设备,所求得的解比之前的解更加好,那么就保持这种设备开启情况,并且继续删去下一个设备。如果所求得的解比之前的更坏,那么我们可以恢复之前删去的设备,并去删去下一个设备。这样,就可以将大部分设备关闭。

以上的贪心策略总结起来就是两条规则:

  • 策略1:将每个人分配到费用最低且容量足够的设备上。
  • 策略2:尝试删去容量分配最少的设备,重新执行策略1。

虽然删去设备、恢复设备这些操作看起来比较像是启发式搜索,不过由于策略是固定的,每次所得到的解也是固定的。

Algorithm

首先实现一个带设备过滤限制的贪心函数,该函数可以将部分设备过滤掉,从剩下的设备种执行策略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
Result greedyWithFilter(const std::vector<Facility> &f, const std::vector<Customer> &c, std::vector<std::pair<int, size_t>> &capacity, const std::vector<bool> &filter) {
Result res;
res.cost = 0;
res.status = std::vector<bool>(f.size());
res.assignment = std::vector<size_t>(c.size());
std::vector<std::vector<std::pair<int, size_t>>> cost(c.size());
for (size_t i = 0; i < c.size(); i++) {
for (size_t j = 0; j < c[i].assignmentCost.size(); j++) {
cost[i].push_back(std::make_pair(c[i].assignmentCost[j], j));
}
std::sort(cost[i].begin(), cost[i].end(), [](std::pair<int, size_t> a, std::pair<int, size_t> b) -> bool {
return a.first < b.first;
});
}
for (size_t i = 0; i < f.size(); i++) {
capacity.push_back(std::make_pair(0, i));
}
for (size_t i = 0; i < c.size(); i++) {
size_t index = 0;
while (index < cost[i].size() && (filter[cost[i][index].second] == false ||
capacity[cost[i][index].second].first + c[i].demand > f[cost[i][index].second].capacity)) {
index++;
}
if (index == cost[i].size()) {
res.cost = 0;
break;
}
if (res.status[cost[i][index].second] == false) {
res.status[cost[i][index].second] = true;
res.cost += f[cost[i][index].second].openingCost;
}
res.assignment[i] = cost[i][index].second;
res.cost += cost[i][index].first;
capacity[cost[i][index].second].first += c[i].demand;
}
return res;
}

接下来,实现贪心函数,负责实现设备删去、设备恢复等逻辑。

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
Result Greedy(const std::vector<Facility> &f, const std::vector<Customer> &c) {
std::vector<bool> filter(f.size());
for (size_t i = 0; i < f.size(); i++) {
filter[i] = true;
}
std::set<size_t> s;
Result best;
best.cost = 0;
size_t last = (size_t) -1;
while (s.size() != f.size()) {
std::vector<std::pair<int, size_t>> capacity;
Result res = greedyWithFilter(f, c, capacity, filter);
if ((res.cost != 0 && res.cost <= best.cost) || best.cost == 0) {
best = res;
} else if (last != (size_t)-1 || res.cost == 0) {
filter[last] = true;
}
std::sort(capacity.begin(), capacity.end(), [](std::pair<int, size_t> a, std::pair<int, size_t> b) -> bool {
return a.first < b.first;
});
size_t index = 0;
while (index < capacity.size() && (filter[capacity[index].second] == false || s.count(capacity[index].second))) {
index++;
}
if (index == capacity.size()) {
break;
}
last = capacity[index].second;
filter[last] = false;
s.insert(last);
}
if (check(f, c, best) == false) {
std::cout << "Error Result" << std::endl;
std::exit(-1);
}
return best;
}

Result

Test CaseResultTime(s)
p191420.001
p281040.001
p398240.001
p4112610.002
p593480.001
p680610.001
p799900.001
p8117900.003
p985980.002
p1076170.002
p1190640.001
p12103010.001
p1385440.007
p1473070.007
p1592760.007
p16110760.008
p1785790.007
p1873420.008
p1991740.008
p20107740.007
p2183970.008
p2273300.007
p2389430.009
p24105430.008
p25121670.044
p26110860.045
p27128860.046
p28146860.047
p29143070.047
p30128520.046
p31152520.045
p32174390.045
p33122240.045
p34112320.047
p35128830.046
p36144830.048
p37115210.055
p38105940.046
p39120670.045
p40132730.046
p4168470.003
p4258430.013
p4354010.021
p4475850.003
p4565230.012
p4661230.022
p4766340.003
p4856150.013
p4955670.022
p5094540.004
p5175760.017
p5295880.003
p5387950.013
p5497020.003
p5581590.014
p56221660.06
p57272660.061
p58395540.064
p59302320.064
p60209740.071
p61251720.065
p62335490.062
p63273190.065
p64208400.064
p65249940.063
p66324420.067
p67270480.069
p68208400.063
p69250050.065
p70338290.061
p71270220.061

Approach #2 Local Search(Hill Climbing)

Intuition

设备选址问题可以用启发式搜索求解,其中局部搜索是一种方法。在这里我采用爬山法来求解CFLP,爬山法属于局部搜索中的一种。

所谓的爬山法,就是从一个初始解出发,从当前解的邻域中找到比该解更好的解,然后将这个更好的解视为当前解。这样一直循环迭代下去,最终会趋于稳定,得到一个局部最优解。因为当前解是一直朝着更低的费用前进,只有向上的行为,所以叫爬山法。

不过局部搜索有一个缺点,就是最终解是一个局部最优解,可能不是整个问题的最优解。

局部搜索的关键在于初始解的生成和搜索策略的实现。通常情况下,初始解是可以随机生成的,但是,局部搜索的收敛速度是很慢的,我们可以基于一个比较好的解出发,而不是随机生成初始解。这里我们采用方法一贪心法所生成的解作为初始解,这样就能保证局部搜索的解一定比贪心法的解要好。

搜索策略的实现就是如何找邻域的问题,在TSP问题中我们可以简单的通过K-opt法来找邻域,但是在CFLP问题中,由于限制比较多,邻域的定义也不那么直观。

我们定义一下的策略来随机生成某个解的邻域:

  • 策略1:将1个人从某个设备移动到另一个设备。
  • 策略2:将不同设备的2个人相互交换。
  • 策略3:将2个设备安排的所有人相互交换。

以上3种策略所生成的解,我们都认为它是当前解的邻解。在局部搜索的每一次迭代中,寻找当前解的邻域中的某个解,通过对比这两个解的费用,来决定当前解是否修改。

Algorithm

这里,我们不再采用前面贪心法修改解的方法,虽然它依靠check来检测错误可以很好找到打码时留下的BUG。我们实现一个setNewCost函数,根据解的消费者安排情况和设备开启情况,来计算新的总费用,并返回该解是否合法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool setNewCost(const std::vector<Facility> &f, const std::vector<Customer> &c, Result &res) {
int cost = 0, capacity[f.size()] = {0};
for (size_t i = 0; i < f.size(); i++) {
if (res.status[i]) {
cost += f[i].openingCost;
}
}
for (size_t i = 0; i < c.size(); i++) {
capacity[res.assignment[i]] += c[i].demand;
if (capacity[res.assignment[i]] > f[res.assignment[i]].capacity) {
return false;
}
cost += c[i].assignmentCost[res.assignment[i]];
}
res.cost = cost;
return true;
}

然后根据上述所提及的3个搜索策略,编写生成邻域的解的代码。生成邻域需要用上随机数生成函数,并使用当前时间作为随机种子。

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
Result generateNeighborSolution(const std::vector<Facility> &f, const std::vector<Customer> &c, Result best) {
std::default_random_engine random(std::chrono::system_clock::now().time_since_epoch().count());
unsigned type = random() % 3;
Result res;
size_t count = 0;
bool flag = false;
switch (type + 1) {
case 1: // 移动1个人
do {
// i - 人, j - 设备
size_t i = random() % c.size(), j = random() % f.size();
if (best.assignment[i] == j) {
flag = true;
continue;
} else {
flag = false;
}
res = best;
size_t last = res.assignment[i];
res.assignment[i] = j;
bool empty = true;
for (size_t k = 0; k < c.size(); k++) {
if (res.assignment[k] == last) {
empty = false;
break;
}
}
if (empty) {
res.status[last] = false;
}
count++;
} while (count < 100 && (flag || setNewCost(f, c, res) == false));
break;
case 2: // 交换2个人
do {
// i - 人A, j - 人B
size_t i = random() % c.size(), j = random() % c.size();
if (i == j || best.assignment[i] == best.assignment[j]) {
flag = true;
continue;
} else {
flag = false;
}
res = best;
size_t tmp = res.assignment[i];
res.assignment[i] = res.assignment[j];
res.assignment[j] = tmp;
count++;
} while (count < 100 && (flag || setNewCost(f, c, res) == false));
break;
case 3: // 交换2个设备
do {
// i - 设备A, j - 设备B
size_t i = random() % f.size(), j = random() % f.size();
if (i == j) {
flag = true;
continue;
} else {
flag = false;
}
res = best;
for (size_t k = 0; k < c.size(); k++) {
if (res.assignment[k] == i) {
res.assignment[k] = j;
} else if (res.assignment[k] == j) {
res.assignment[k] = i;
}
}
count++;
} while (count < 100 && (flag || setNewCost(f, c, res) == false));
break;
}
return res;
}

接下来实现局部搜索的迭代部分,循环次数我们可以设置为$30*(|Facility|+|Customer|)$,这样可以保证不同大小的数据都能得到适合的迭代次数。

1
2
3
4
5
6
7
8
9
10
Result LocalSearch(const std::vector<Facility> &f, const std::vector<Customer> &c) {
Result best = Greedy(f, c);
for (size_t i = 0; i < 30 * (f.size() + c.size()); i++) {
Result res = generateNeighborSolution(f, c, best);
if (best.cost > res.cost) {
best = res;
}
}
return best;
}

Result

Test CaseResultTime(s)
p190550.017
p280170.02
p395500.021
p4107780.02
p592130.016
p679950.017
p799130.018
p8116550.016
p985980.016
p1076170.017
p1190640.016
p12101380.017
p1385440.027
p1472000.026
p1592490.026
p16110490.026
p1784590.027
p1872460.026
p1990580.029
p20107120.028
p2181730.025
p2273300.025
p2389430.024
p24105430.024
p25120360.129
p26109510.13
p27126620.146
p28145410.129
p29133430.13
p30120010.137
p31142960.133
p32161080.137
p33118490.134
p34110110.132
p35124740.132
p36140790.133
p37113290.131
p38105940.124
p39120670.126
p40130700.125
p4168470.038
p4257720.046
p4353730.055
p4474850.042
p4565150.045
p4660160.055
p4764820.04
p4856130.045
p4953690.056
p5089110.048
p5175450.063
p5295880.05
p5387950.06
p5492960.052
p5581580.058
p56218480.216
p57271890.199
p58390460.231
p59292220.222
p60209340.182
p61250360.186
p62333580.201
p63272410.183
p64206200.185
p65248880.181
p66321550.203
p67262340.196
p68207200.193
p69248990.201
p70335140.211
p71269330.204

Approach #3 Simulated Annealing

Intuition

通过上面两种方法,可以发现爬山法的费用跟贪心的费用相比有10%~15%的提升。不过,爬山法这类局部搜索方案很容易达到局部最优解,而没有办法求解更加好的解。

模拟退火是在局部搜索的基础上进行优化的启发式搜索方法,能够使得当前解有一定概率恶化,从而避免局部最优解。

我们可以设置一个初始温度,每次求邻域的解之后,对比当前解和邻域中的解的能量差。如果能量差为负,那就允许当前解变化。如果能量差为正,根据当前温度计算出一个概率值,有一定概率允许当前解变化。此时,当前解的费用是低于邻域解的,因此这种解的变化实际上是一种恶化。

我们取$R$为$[0,1]$中的任意一个实数,即随机值,取$P=e^{- \frac{\Delta E}{T} }$。如果$R<P$,那么我们就认为当前解可以恶化。

每次处理完解之后,当前温度将按降温系数的限制来降温,当温度降低到一定程度之后,即达到了终止温度之后,迭代结束。

模拟退火比较繁琐的一步是选取初始温度和降温系数,这里采用的初始温度为500,降温系数为0.96。

Algorithm

模拟退火是在局部搜索的基础上优化的,实际上,生成邻域的代码可以完全照搬局部搜索的,我们只需要修改迭代一部分的代码。

首先定义初始温度、终止温度、降温系数。

1
2
3
4
5
namespace simulated_annealing {
const double T_START = 500; // 初始温度
const double T_END = 0.000001; // 终止温度
const double Q = 0.9; // 降温系数
}

接下来实现降温操作、解恶化等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Result SimulatedAnnealing(const std::vector<Facility> &f, const std::vector<Customer> &c) {
Result best = Greedy(f, c);
double t = T_START;
while (t > T_END) {
for (size_t i = 0; i < 10 * (f.size() + c.size()); i++) {
Result res = generateNeighborSolution(f, c, best);
if (best.cost > res.cost) {
best = res;
} else {
std::default_random_engine random(std::chrono::system_clock::now().time_since_epoch().count());
std::uniform_real_distribution<> dist(0, 1);
double r = dist(random);
double p = std::exp((double)(best.cost - res.cost) / t);
if (r < p) {
best = res;
}
}
}
t *= Q;
}
return best;
}

Result

Test CaseResultTime(s)
p189851.379
p279261.372
p395131.363
p4111211.528
p591981.249
p678871.376
p798871.235
p8115221.285
p984771.15
p1076481.092
p1193611.145
p12108261.149
p1388421.591
p1475201.559
p1592881.596
p16110911.814
p1784521.614
p1872791.572
p1991131.529
p20112981.579
p2181441.5
p2273161.497
p2391821.476
p24112741.497
p25126896.996
p26116036.664
p27140096.644
p28164236.698
p29126517.061
p30118966.813
p31145986.842
p32177746.755
p33120286.887
p34115816.441
p35144686.808
p36163816.492
p37122006.428
p38112826.353
p39139786.334
p40156806.694
p4169452.669
p4273342.696
p4366552.806
p4471593.063
p4566792.708
p4670023.161
p4763163.158
p4862382.821
p4958252.871
p5092753.472
p5181323.91
p5294493.545
p5396283.369
p5492733.783
p5581573.552
p56230569.787
p573089610.34
p58467689.59
p59361279.55
p60227419.691
p61306489.682
p62464259.557
p63319379.388
p64233469.413
p65303619.376
p66453899.597
p67343019.263
p68226099.889
p692972911.412
p704775510.906
p713129513.429

Solution Result

1545496983687

以上是局部搜索的样例1-5的输出,其中每个样例的前三行为当前解,而最后一行为与本程序执行的最优解做比较。

如果需要查看其他样例的最优解,可以前往GitHub查看。

可执行脚本编译运行程序。

1
2
$ ./build.sh
$ ./cflp

Conclusion

本次用了贪心法、爬山法、模拟退火三种方法来解决CFLP问题,其中,基于贪心法的解作为初始解的爬山法的解是最优的,并且相比贪心法,费用降低了10%~15%左右。

而基于爬山法的模拟退火,可能是因为初始温度和温度系数的把控不当,模拟退火的解实际比爬山法还要差,并且及其不稳定。有时候模拟退火的解非常接近爬山法的解,而有时候解比贪心法还要差。

在经过多次修改之后,部分样例的模拟退火法可以求得更好的解,但是接近一半的样例还是比爬山法要差。不过相比贪心法已经有了一定提升。

土豪与Zhenly通道
0%