有关贪心算法的练习题整体的归纳与总结
算法理解
贪心：对问题进行求解时，每一步都采取最优的选择；近似最优解；
- 数学模型
- 原问题->子问题
- 得到子问题的局部最优解
- 把局部最优解整合成整个问题的近似最优解
（集合覆盖问题、旅行商问题）eg.
FatMouse’ Trade：算出比例，从大到小排列，选择；
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
| #include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
struct node
{
int x;
int y;
int t;
}JF[1000];
bool cmp(node a,node b)
{
double xx=(double)a.x/a.y;
double yy=(double)b.x/b.y;
return xx>yy;
}
int main()
{
int m,n;
while(scanf("%d%d",&m,&n)!=EOF&&m!=-1&&n!=-1){
for(int i=0;i<n;i++){
cin>>JF[i].x>>JF[i].y;
JF[i].t=i;
}
sort(JF,JF+n,cmp);
int sum=0;int i;
for(i=0;i<n;i++){
if(m>=JF[i].y){
sum+=JF[i].x;
m=m-JF[i].y;
}
else break;
}
double tmp;
if(m!=0&&i!=n)tmp=(double)(JF[i].x*m)/JF[i].y+sum;
else tmp=(double)sum;
printf("%.3lfn",tmp);
/*for(int i=0;i<n;i++){
cout<<JF[i].t<<" "<<JF[i].x<<" "<<JF[i].y<<endl;
}*/
}
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
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
| #include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
char maze[5][5];
int num;
struct node
{
int x;
int y;
int value;
}flag[20];
bool cmp(node a,node b)
{
return a.value<b.value;
}
bool fire(node n)
{
int x=n.x;
int y=n.y;
int i,j;
for(i=0;i<num;i++){
if(maze[i][y]=='f'){
//证明i与x之间没有墙
int up,down;
if(i>x){
up=x;
down=i;
}
else {
up=i;down=x;
}
int tmp=up+1;
//if(tmp==down)break;
for(;tmp<down;tmp++){
if(maze[tmp][y]=='X')break;
}
if(tmp==down)break;
}
}
if(i!=num)return false;
for(j=0;j<num;j++){
if(maze[x][j]=='f'){
//证明j与y之间没有墙
int l,r;
if(j<y){
l=j;
r=y;
}
else {
l=y;r=j;
}
int tmp=l+1;
//if(tmp==r)break;
for(;tmp<r;tmp++){
if(maze[x][tmp]=='X')break;
}
if(tmp==r)break;
}
}
if(j!=num)return false;
return true;
}
int main()
{
while(scanf("%d",&num)!=EOF&&num!=0){
for(int i=0;i<num;i++){
for(int j=0;j<num;j++)
cin>>maze[i][j];
}
for(int i=0;i<num;i++){
for(int j=0;j<num;j++){
//cout<<maze[i][j];
int t=i*num+j;
flag[t].x=i;
flag[t].y=j;
//设计贪心依据数组
if(maze[i][j]=='X'){
flag[t].value=0;
}
else {
int count=1;
//往上
for(int a=i-1;a>=0;a--){
if(maze[a][j]=='X')break;
count++;
}
//往下
for(int a=i+1;a<num;a++){
if(maze[a][j]=='X')break;
count++;
}
//往左
for(int b=j-1;b>=0;b--){
if(maze[i][b]=='X')break;
count++;
}
//往右
for(int b=j+1;b<num;b++){
if(maze[i][b]=='X')break;
count++;
}
flag[t].value=count;
}
//cout<<flag[t].value;
}
//cout<<endl;
}
//从小到大排序
sort(flag,flag+num*num,cmp);
//for(int i=0;i<num*num;i++)cout<<flag[i].value<<" ";
//贪心选择
int sum=0;
for(int i=0;i<num*num;i++){
if(flag[i].value!=0){//排除墙
if(fire(flag[i]))
{
sum++;
maze[flag[i].x][flag[i].y]='f';//已放置标记
//cout<<flag[i].x<<" "<<flag[i].y<<" "<<flag[i].value<<endl;
}
}
}
cout<<sum<<endl;
}
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
48
49
50
51
52
53
54
| #include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
bool vis[5000];
struct node
{
int l;
int w;
}wood[5000];
bool cmp(node x,node y)
{
if(x.l==y.l){
return x.w<y.w;
}
return x.l<y.l;
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
int num;
int sum=0;
scanf("%d",&num);
memset(vis,0,sizeof(vis));
for(int i=0;i<num;i++){
cin>>wood[i].l>>wood[i].w;
}
sort(wood,wood+num,cmp);
for(int i=0;i<num;i++){
//cout<<wood[i].l<<" "<<wood[i].w<<endl;
if(vis[i])continue;//访问完跳过
//因为l已经从小到大排序过
//因此关注w
int curw=wood[i].w;
for(int j=i+1;j<num;j++){
if(!vis[j]&&curw<=wood[j].w){
//cout<<"ok";
vis[j]=1;//标记访问
curw=wood[j].w;
}
}
sum++;
}
cout<<sum<<endl;
}
return 0;
}
|