算法的乐趣之贪婪法

发布 : 2019-03-24 浏览 :

贪婪法(Greedy Algorithm)

贪婪法(Greedy Algorithm),又称贪心算法,是寻找最优解问题的常用方法,这种方法模式一般将求解过程分成若干个步骤,但每个步骤都应用贪心原则,选取当前状态下最好的或最优的选择(局部最有利的选择),并以此希望最后堆叠出的结果也是最好或最优的解。因为不进行回溯处理,贪婪法只在很少的情况下可以得到真正的最优解,比如最短路径问题、图的最小生成树问题。在大多数情况下,由于选择策略的“短视”,贪婪法会错过真正的最优解,而得不到问题的真正答案。但是贪婪法简单、高效,省去了为找最优解可能需要的穷举操作,可以得到与最优解比较接近的近似最优解,通常作为其他算法的辅助算法来使用。

当然,对于一些能够证明贪婪策略得到的就是最优解的问题,应用贪婪法可以高效地求得结果,比如求最小生成树的 Prim 算法和 Kruskal 算法。事实上,在任何算法中,只要在某个阶段使用了只考虑局部最优情况的选择策略,都可以理解为使用了贪婪算法。

贪婪法的基本设计思想有以下三个步骤:

  • 建立对问题精确描述的数学模型,包括定义最优解的模型;
  • 将问题分解为一系列的子问题,同时定义子问题的最优解结构;
  • 应用贪心原则确定每个子问题的局部最优解,并根据最优解的模型,用子问题的局部最优解堆叠出全局最优解。

0-1 贪婪法的例子:0-1 背包问题背包问题

核心代码如下:
spFunc:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Choosefunc1(std::vector<OBJECT>& objs, int c)
{
int index = -1;
int mp = 0;
for(int i = 0; i < static_cast<int>(objs.size()); i++)
{
if((objs[i].status == 0) && (objs[i].price > mp))
{
mp = objs[i].price;
index = i;
}
}

return index;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void GreedyAlgo(KNAPSACK_PROBLEM *problem, SELECT_POLICY spFunc)
{
int idx;
int ntc = 0;

//spFunc 每次选最符合策略的那个物品,选后再检查
while((idx = spFunc(problem->objs, problem->totalC - ntc)) != -1)
{
//所选物品是否满足背包承重要求?
if((ntc + problem->objs[idx].weight) <= problem->totalC)
{
problem->objs[idx].status = 1;
ntc += problem->objs[idx].weight;
}
else
{
//不能选这个物品了,做个标记后重新选
problem->objs[idx].status = 2;
}
}

PrintResult(problem->objs);
}\

完整代码如下:

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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
// knapsack.cpp : Defines the entry point for the console application.
//
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

typedef struct tagObject
{
int weight;
int price;
int status; //0:未选中;1:已选中;2:已经不可选
}OBJECT;

typedef struct tagKnapsackProblem
{
std::vector<OBJECT> objs;
int totalC;
}KNAPSACK_PROBLEM;

typedef int (*SELECT_POLICY)(std::vector<OBJECT>& objs, int c);

int Choosefunc1(std::vector<OBJECT>& objs, int c)
{
int index = -1;
int mp = 0;
for(int i = 0; i < static_cast<int>(objs.size()); i++)
{
if((objs[i].status == 0) && (objs[i].price > mp))
{
mp = objs[i].price;
index = i;
}
}

return index;
}

int Choosefunc2(std::vector<OBJECT>& objs, int c)
{
int index = -1;
int mw = 10000;
for(int i = 0; i < static_cast<int>(objs.size()); i++)
{
if((objs[i].status == 0) && (objs[i].weight < mw))
{
mw = objs[i].weight;
index = i;
}
}

return index;
}

int Choosefunc3(std::vector<OBJECT>& objs, int c)
{
int index = -1;
double ms = 0.0;
for(int i = 0; i < static_cast<int>(objs.size()); i++)
{
if(objs[i].status == 0)
{
double si = objs[i].price;
si = si / objs[i].weight;
if(si > ms)
{
ms = si;
index = i;
}
}
}

return index;
}

void PrintResult(std::vector<OBJECT>& objs)
{
int totalW = 0;
int totalP = 0;
for(int i = 0; i < static_cast<int>(objs.size()); i++)
{
if(objs[i].status == 1)
{
totalW += objs[i].weight;
totalP += objs[i].price;
std::cout << "object " << i + 1 << ": weight=" << objs[i].weight <<
", price=" << objs[i].price << std::endl;
}
}
std::cout << "total weight : " << totalW << ", total price : " << totalP << std::endl;
}

void GreedyAlgo(KNAPSACK_PROBLEM *problem, SELECT_POLICY spFunc)
{
int idx;
int ntc = 0;

//spFunc 每次选最符合策略的那个物品,选后再检查
while((idx = spFunc(problem->objs, problem->totalC - ntc)) != -1)
{
//所选物品是否满足背包承重要求?
if((ntc + problem->objs[idx].weight) <= problem->totalC)
{
problem->objs[idx].status = 1;
ntc += problem->objs[idx].weight;
}
else
{
//不能选这个物品了,做个标记后重新选
problem->objs[idx].status = 2;
}
}

PrintResult(problem->objs);
}

const int MIN=0x80000000;
const int N=7; //物品数量
const int V=150; //背包容量
int f[N+1][V+1];

int Package(int *W,int *C,int N,int V)
{
int i,j;
memset(f,0,sizeof(f)); //初始化为0

for(i=0;i<=N;i++)
for(j=1;j<=V;j++) //此步骤是解决是否恰好满足背包容量,
f[i][j]=MIN; //若“恰好”满足背包容量,即正好装满背包,则加上此步骤,若不需要“恰好”,则初始化为0

for(i=1;i<=N;i++)
for(j=C[i];j<=V;j++)
{
f[i][j]=(f[i-1][j]>f[i-1][j-C[i]]+W[i])?f[i-1][j]:(f[i-1][j-C[i]]+W[i]);
std::cout<<"f["<<i<<"]["<<j<<"]="<<f[i][j]<<std::endl;
}
return f[N][V];
}

void DPAlgo()
{
int W[8]={0,10,40,30,50,35,40,30}; //物品权重
int C[8]={0,35,30,60,50,40,10,25}; //物品大小
int result=Package(W,C,N,V);
if(result>0)
{
std::cout<<std::endl;
std::cout<<"the opt value:"<<result<<std::endl;
int i=N,j=V;
while(i)
{
if(f[i][j]==(f[i-1][j-C[i]]+W[i]))
{
std::cout<<i<<":"<<"w="<<W[i]<<",c="<<C[i]<<std::endl;
j-=C[i];
}
i--;
}
}
else
std::cout<<"can not find the opt value"<<std::endl;
}

OBJECT objects[] = { {35,10,0}, {30,40,0}, {60,30,0}, {50,50,0},
{40,35,0}, {10,40,0}, {25,30,0} };

int main(int argc, char* argv[])
{

KNAPSACK_PROBLEM problem;

problem.objs.assign(objects, objects + 7);
problem.totalC = 150;

//GreedyAlgo(&problem, Choosefunc1);
//GreedyAlgo(&problem, Choosefunc2);
//GreedyAlgo(&problem, Choosefunc3);
DPAlgo();

return 0;
}
本文作者 : HeoLis
原文链接 : http://ishero.net/算法的乐趣之贪婪法.html
版权声明 : 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!

学习、记录、分享、获得

微信扫一扫, 向我投食

微信扫一扫, 向我投食