Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

贪心算法习题

Posted on Edited on In ,
Symbols count in article: 4.6k Reading time ≈ 4 mins.

活动教室分配

T16.1-4 活动教室分配(区间着色问题)

题目：

　　有一组活动，我们需要将它们安排到一些教室，任意活动都可以在任意教室进行。我们希望使用最少的教室完成所有活动。

　　设计一个高效的贪心算法求每个活动应该在哪个教室进行。

分析：

　　本题是对书中活动选择问题的一个扩展。在活动选择问题中，我们要求的是一个最大兼容活动集，也就是在所有时间内时间不重叠的最多的活动集合。

　　易知，这样一个活动集，就是一个教室最多能够举办的活动集。所以剩下的活动一定不能和该活动集内的活动在同一个教室举行。我们不断对剩下的活动使用贪心算法，需要多少次贪心能够选取完所有的活动，就最少需要几个教室。

　　我们首先对所有活动按结束时间排序。遍历所有活动，如果下一个活动开始时间比某教室中最后一个活动结束时间晚，则加入该教室。如果不能加入已使用的任何教室，则需要新开一个教室。 　　

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
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

typedef pair<int,int> Acti;//用起始时间和结束时间的pair表示一个活动。

void party(vector<Acti>& acti_vec)
{
    sort(acti_vec.begin(),acti_vec.end(),[](const Acti& a,const Acti& b){return a.second < b.second;});//按结束时间对所有活动排序。
    vector<vector<Acti>> classroom;//教室列表。
    vector<Acti> classroom1;
    classroom1.push_back(*acti_vec.begin());//初始化第一个教室，将结束时间最早的活动放入。
    classroom.push_back(classroom1);//将第一个教室加入教室列表。
    for(int i = 1;i<(int)acti_vec.size();i++)//遍历一遍活动列表。
    {
        int j;
        for(j = 0;j < (int)classroom.size();j++)
        {
            if(acti_vec[i].first >= (*(classroom[j].end()-1)).second)//如果该活动的开始时间比某教室目前为止最后一个活动结束结束时间晚，则加入该教室。
            {
                classroom[j].push_back(acti_vec[i]);
                break;
            }
        }
        if(j == (int)classroom.size())//如果无法加入当前任何一个教室，则需要一个新的教室。
        {
            vector<Acti> classroom_temp;
            classroom_temp.push_back(acti_vec[i]);
            classroom.push_back(classroom_temp);
        }

    }

    for(int i = 0;i < (int)classroom.size();i++)//对每一个教室，按起始时间 结束时间输出每一个活动。
    {
        cout<<"classroom "<<i+1<<":"<<endl;
        for(int j = 0;j < (int)classroom[i].size();j++)
        {
            cout<<classroom[i][j].first<<" "<<classroom[i][j].second<<endl;
        }
    }
}

int main()
{
    vector<Acti> acti_vec = {
                            {1,4},
                            {3,5},
                            {0,6},
                            {5,7},
                            {3,9},
                            {5,9},
                            {6,10},
                            {8,11},
                            {8,12},
                            {2,14},
                            {12,16}
                            };
    party(acti_vec);
    return 0;
}

找零问题

题目：
考虑用最少的硬币找n美分零钱的问题。假设每种硬币的面额都是整数。

A.设计贪心算法求解找零问题，假定有25美分、10美分、5美分和1美分4种面额的硬币。证明你的算法能找到最优解。

B.假定硬币的面额是c的幂，即面额c0,c1,…,ck,c和k为整数，c>1,k>=1.证明：贪心算法总能得到最优解。

C.设计一组硬币面额，使得贪心算法不能保证得到最优解。这组硬币面额中应该包含1美分，使得对每个零钱值都存在找零方案。

D.设计一个O(nk)时间的找零算法，适用于任何k种不同面额的硬币，假定问题包含1美分硬币。

分析:

A：

引理1（离散数学其及应用3.1.4）：若n是正整数，则用25美分、10美分、5美分和1美分等尽可能少的硬币找出的n美分零钱中，至多有2个10美分、至多有1个5美分、至多有4个1美分硬币，而不能有2个10美分和1个5美分硬币。用10美分、5美分和1美分硬币找出的零钱不能超过24美分。

证用反证法。证明如果有超过规定数目的各种类型的硬币，就可以用等值的数目更少的硬币来替换。注意，如果有3个10美分硬币，就可以换成1个25美分和1个5美分硬币；如果有2个5美分硬币，就可以换成1个10美分硬币；如果有5个1美分硬币，就可以换成1个5美分硬币；如果有2个10美分和1个5美分硬币，就可以换成1个25美分硬币。由于至多可以有2个10美分、1个5美分和4个1美分硬币，而不能有2个10美分和1个5美分硬币，所以当用尽可能少的硬币找n美分零钱时，24美分就是用10美分、5美分和1美分硬币能找出的最大值。

假设存在正整数n，使得有办法将25美分、10美分、5美分和1美分硬币用少于贪心算法所求出的硬币去找n美分零钱。首先注意，在这种找n美分零钱的最优方式中使用25美分硬币的个数q′，一定等于贪心算法所用25美分硬币的个数。为说明这一点，注意贪心算法使用尽可能多的25美分硬币，所以q′≤q。但是q′也不能小于q。假如q′小于q，需要在这种最优方式中用10美分、5美分和1美分硬币至少找出25美分零钱。而根据引理1，这是不可能的。由于在找零钱的这两种方式中一定有同样多的25美分硬币，所以在这两种方式中10美分、5美分和1美分硬币的总值一定相等，并且这些硬币的总值不超过24美分。10美分硬币的个数一定相等，因为贪心算法使用尽可能多的10美分硬币。而根据引理1，当使用尽可能少的硬币找零钱时，至多使用1个5分硬币和4个1分硬币，所以在找零钱的最优方式中也使用尽可能多的10美分硬币。类似地，5美分硬币的个数相等；最终，1美分的个数相等。

B：

分析——同A题，由于1+c1+c2+c3+…ck-1=ck - 1<ck,故当n大于ck时，可以分解为ck与n-ck的值，其中ck只用一个硬币值为ck的硬币就能得到最少硬币数，而子问题变成n-ck的最少硬币数，依次类推，贪心算法总能得到最好的结果。

C:
分析——要分析什么情况下贪心算法无效，如果出现一组硬币25，6，5，1.由于1+5=6，当遇到10元时，按照贪心算法将分解为6+41，而其实为25.

D：
假设m(n)表示找零n美分需要的最少硬币数，硬币面值为c1,c2, …,ck，并令m[0]=0,则m(n)=1如果n等于某个ci，否则m(n) =min{ m(n-c1)+1, m(n-c2)+1, …, m(n-ck)+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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#include <iostream>
#include <vector>
using namespace std;

void change(vector<int>c,vector<int>&m,vector<int>&s,int n)
{
	int k = c.size()-1;//减掉填充符
	m[0] = 0;
	for(int i=1;i<=n;i++)
	{
		m[i] = 2147483647;
		for(int j=1;j<=k && (i>=c[j]);j++)
		{
			if(m[i-c[j]]+1< m[i])
			{
				m[i] = m[i-c[j]]+1;
				s[i] = j;
			}
		}
	}
}

void print(vector<int>c,vector<int>s,int n,int count)
{
	int k = c.size();
	vector<int>number(k);
	for(int i=1;i<k;i++)
		number[i] = 0;
	while(n != 0)
	{
		number[s[n]] ++;
		n = n - c[s[n]];
	}
	printf("needs coins : %d \n",count);
	for(int i=k-1;i>=1;i--)
	{
		if(number[i] > 0)
			printf("need %d %d cents coin  ",number[i],c[i]);
	}
	cout<<endl;
}
int main()
{
	//const int c1[] = {0,1,5,10,25};//零钱种类 第一个元素0起填充的作用 方便下标处理
	const int c1[] = {0,1,7,10};
	int k = sizeof(c1)/sizeof(int);
	int n = 15;//所需找零钱数
	vector<int>c;
	for(int i=0;i<k;i++)
		c.push_back(c1[i]);
	vector<int>m(n+1);//不同零钱数对应的最小硬币数
	vector<int>s(n+1);//记录所选硬币
	change(c,m,s,n);
	print(c,s,n,m[n]);
}