ACM 贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

例题

钱币找零问题

假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？

代码

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
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

const int N=7;
int Count[N]={3,0,2,1,0,3,5};
int Value[N]={1,2,5,10,20,50,100};

int main()
{
	int money;
	scanf("%d", &money);

	int num = 0;
	for(int i=N-1;i>=0;i--)
	{
		int c=min(money/Value[i],Count[i]);
		money=money-c*Value[i];
		num+=c;
	}

	if(num!=-1) printf("%d\n", num);
	else printf("NO\n");
}

可分割背包问题

有一个背包，背包容量是M，有N个物品，要求尽可能让装入背包中的物品总价值最大，但不能超过总容量，物品可以只取一部分。

输入
第一行输入一个正整数n（1<=n<=5）,表示有n组测试数据；
随后有n测试数据，每组测试数据的第一行有两个正整数s，m（1<=s<=10）;s表示有s个物品。接下来的s行每行有两个正整数v，w，分别表示物品的单位价值和总质量。
输出
输出每组测试数据中背包内的物品的价值和，每次输出占一行。
样例输入

1
2
3
4
5
1
3 15
5 10
2 8
3 9

样例输出

1
65

代码

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 <stdio.h>
#include <algorithm>
using namespace std;

#define MAXN 10000

int main(int argc, char const *argv[])
{
    int T;
    scanf("%d", &T);

    while (T--)
    {
        int n, m;
        int v[MAXN], w[MAXN];

        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%d%d", &v[i], &w[i]);

        for (int i = 0; i < n - 1; i++)
            for (int j = 0; j < n - i - 1; j++)
                if (v[j] < v[j + 1])
                {
                    int temp = v[j];
                    v[j] = v[j + 1];
                    v[j + 1] = temp;

                    temp = w[j];
                    w[j] = w[j + 1];
                    w[j + 1] = temp;
                }

        int ans = 0;
        for (int i = 0; i < n; i++)
        {
        	if (w[i] >= m)
        	{
        		ans += m * v[i];
        		m = 0;
        		break;
        	}
        	else
        	{
        		ans += w[i] * v[i];
        		m -= w[i];
        	}
        }

        printf("%d\n", ans);
    }

    return 0;
}

排序

冒泡排序

1
2
3
4
5
6
7
8
for (int i = 0; i < len - 1; i++)
    for (int j = 0; j < len - 1 - i; j++)
        if (arr[j] > arr[j + 1])
        {
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }

选择排序

1
2
3
4
5
6
7
8
9
10
for(i = 0; i < n-1; i++)
{
    min = i;//查找最小值
    for(j = i+1; j<n; j++)
        if(A[min] > A[j])
            min = j;
    
    if(min != i)
        swap(&A[min], &A[i]);
}

其他排序

已经帮你们百度好的链接

建议用C++的 algorithm 头文件中的 sort 函数，也是ACM中最常用的排序算法。

缺点

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

⑴贪心策略：总价值最大

反例：

W=30
物品：A B C
重量：28 12 12
价值：30 20 20

根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。

⑵贪心策略：重量最小

它的反例与第一种策略的反例差不多。

⑶贪心策略：单位量价值最大

反例：

W=30
物品：A B C
重量：28 20 10
价值：28 20 10

根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。

【注意：如果物品可以分割为任意大小，那么策略3可得最优解】

(4)DP问题（动态规划）

W=40
物品：A B C
重量：25 20 15
价值：25 20 15

这需要DP。

题目

今年暑假不AC（节目表）

“今年暑假不AC？”
“是的。”
“那你干什么呢？”
“看世界杯呀，笨蛋！”
“@#$%^&*%…”

确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。
作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）

Input

输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。

Output

对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
12 
1 3 
3 4 
0 7 
3 8 
15 19 
15 20 
10 15 
8 18 
6 12 
5 10 
4 14 
2 9 
0

Sample Output 

1
5

代码（HDU 2037）

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
#include<stdio.h>
int main(int argc, const char *argv[])
{

    int i, n, j, tmp;

    while (scanf("%d", &n) != EOF && n != 0)
    {
        int count = 1, a[100] = {0}, b[100] = {0};
        for (i = 0; i < n; i++)
            scanf("%d %d", &a[i], &b[i]);

        for (i = 0; i < (n - 1); i++)
        {
            for (j = 0; j < (n - 1 - i); j++)
            {
                if (b[j] > b[j + 1])
                {
                    tmp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = tmp;

                    tmp = b[j];
                    b[j] = b[j + 1];
                    b[j + 1] = tmp;
                }
            }
        }

        int time = 0;
        for (i = 1; i < n; i++)
        {
            if (a[i] >= b [time])
            {
                time = i;
                count++;
            }
        }
        printf("%d\n", count);
    }
    return 0;
}

阶乘之和

描述
给你一个非负数整数n，判断n是不是一些数（这些数不允许重复使用，且为正数）的阶乘之和，如9=1！+2!+3!，如果是，则输出Yes，否则输出No；

输入
第一行有一个整数0<m<100,表示有m组测试数据；
每组测试数据有一个正整数n<1000000;
输出
如果符合条件，输出Yes，否则输出No;
样例输入

1
2
29
10

样例输出

1
2
Yes
No

喷水装置（一）

描述
现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0<Ri<15)的圆被湿润，这有充足的喷水装置i（1<i<600)个，并且一定能把草坪全部湿润，你要做的是：选择尽量少的喷水装置，把整个草坪的全部湿润。

输入
第一行m表示有m组测试数据
每一组测试数据的第一行有一个整数数n，n表示共有n个喷水装置，随后的一行，有n个实数ri，ri表示该喷水装置能覆盖的圆的半径。

输出
输出所用装置的个数

样例输入

1
2
3
4
5
2
5
2 3.2 4 4.5 6 
10
1 2 3 1 2 1.2 3 1.1 1 2

样例输出

1
2
2
5

> 喷水装置（二）

改成二维，输入装置个数n、草坪宽 w、高 h（实数），以及每个喷水装置的横坐标和半径。其余题意同上一题。

过河问题

描述
在漆黑的夜里，N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，N个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，N人所需要的时间已知；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这N人尽快过桥。

输入
第一行是一个整数T(1<=T<=20)表示测试数据的组数
每组测试数据的第一行是一个整数N(1<=N<=1000)表示共有N个人要过河
每组测试数据的第二行是N个整数Si,表示此人过河所需要花时间。(0<Si<=100)
输出
输出所有人都过河需要用的最少时间
样例输入

1
2
3
1
4
1 2 5 10

样例输出

1
17