实验6-1 硬币找钱问题—贪心
问题描述：
设有6 种不同面值的硬币，各硬币的面值分别为5 分，1 角，2 角，5 角，1 元，2 元。现要用这些面值的硬币来购物和找钱。购物时可以使用的各种面值的硬币个数存于数组Coins［1:6 ］中，商店里各面值的硬币有足够多。在1 次购物中希望使用最少硬币个数。
例如，1 次购物需要付款0.55 元，没有5 角的硬币，只好用2*20+10+5 共4 枚硬币来付款。如果付出1 元，找回4 角5 分，同样需要4 枚硬币。但是如果付出1.05 元（1 枚1 元和1 枚5 分），找回5 角，只需要3 枚硬币。这个方案用的硬币个数最少。
编程任务：
对于给定的各种面值的硬币个数和付款金额，编程计算使用硬币个数最少的交易方案。
数据输入：
由文件input.txt 给出输入数据。每一行有6 个整数和1 个有2 位小数的实数。分别表示
可以使用的各种面值的硬币个数和付款金额。文件以6 个0 结束。
结果输出:
将编程计算出的最少硬币个数输出到文件output.txt 。结果应分行输出，每行一个数据。如果不可能完成交易，则输出”impossible”。
输入文件示例
input.txt
2 4 2 2 1 0 0.95
2 4 2 0 1 0 0.55
0 0 0 0 0 0
输出文件示例
output.txt
2
3
#include<bits/stdc++.h>
const int N = 20000 ;
int ch[N];
int dp[N]; // dp[i]为当前拥有的硬币数量条件下表示面值为i的最少硬币个数
int v[ 6 ] = { 1 , 2 , 4 , 10 , 20 , 40 }; // 每种硬币对应面值，依次为1，2,4,10,20,40个五分，即5,10,20,50,100,200；
int nm[ 6 ]; // 对应于当前拥有的每种硬币个数
void init() // 计算ch[i]
{
int i,j;
for (i = 0 ;i < N;i ++ )ch[i] =- 1 ;
ch[ 0 ] = 0 ;
for (i = 0 ;i < 6 ;i ++ )
{
for (j = v[i];j < N;j ++ )
{
if (ch[j - v[i]] !=- 1 )
{
int temp = ch[j - v[i]] + 1 ;
if (ch[j] ==- 1 || temp < ch[j])ch[j] = temp;
}
}
}
}
int main()
{
init();
while (scanf( " %d%d%d%d%d%d " , & nm[ 0 ], & nm[ 1 ], & nm[ 2 ], & nm[ 3 ], & nm[ 4 ], & nm[ 5 ]) != EOF)
{
int sum = 0 ;
int kk;
for (kk = 0 ;kk < 6 ;kk ++ )sum += nm[kk];
if (sum == 0 ) break ;
double weight;
scanf( " %lf " , & weight);
weight = weight * 100 ;
int w = int (weight + 0.0000001 );
if (w % 5 != 0 )
{
printf( " impossible\n " );
continue ;
}
else
w = w / 5 ;
int i,j;
memset(dp, - 1 , sizeof (dp));
dp[ 0 ] = 0 ;
int bigger = 0 ;
for (i = 0 ;i < 6 ;i ++ )//计算顾客支付面值i需要的最少硬币数dp[i]
{
while (nm[i] -- )
{
bigger = bigger + v[i];
for (j = bigger;j >= v[i];j -- )
{
if (dp[j - v[i]] !=- 1 )
{
int temp = dp[j - v[i]] + 1 ;
if (dp[j] ==- 1 || temp < dp[j])
{
dp[j] = temp;
}
}
}
}
}
int ans =- 1 ;
for (i = w;i <= bigger;i ++ )//寻找最少硬币组合
{
if (dp[i] !=- 1 )
{
int need = i - w;
if (ch[need] !=- 1 )
{
int temp = dp[i] + ch[need];
if (ans ==- 1 || ans > temp)ans = temp;
}
}
}
if (ans !=- 1 )
printf( " %d\n " ,ans);
else
printf( " impossible\n " );
}
return 0 ;
}解决思路：
首先，我们要明确一下贪心算法的思想：每次尽可能选取面值最大的硬币，直到无法选取为止。这样可以保证找钱的硬币数量最少。
根据这个思想，我们可以先对硬币的面值按照从大到小的顺序进行排列，即2元、1元、5角、2角、1角和5分。然后，对于需要找的钱数，
我们从大到小依次考虑每种面值的硬币，先使用尽可能多的最大面值硬币，然后再考虑次大面值硬币，以此类推，直到钱数为0为止。
具体的步骤如下：
1.对硬币面值进行排序，顺序为2元，1元，5角，2角，1角，5分]。
2.对于需要找的钱数，从大到小依次考虑每种面值的硬币。
3.对于每种面值的硬币，先使用尽可能多的最大面值硬币，直到这种面值的硬币用完或者钱数不足该面值硬币的数量。
4.如果该种面值的硬币用完了，就考虑下一种面值的硬币。
5.重复以上步骤，直到钱数为0为止。
需要注意的是，在使用每种面值的硬币时，我们需要判断当前购物时可用的该种面值硬币数量是否足够，如果不够，则需要向下一种面值
的硬币继续考虑。
在实际操作中，我们可以设计一个循环，每次选择当前最大面值的硬币，然后扁历整个硬币数组，依次从当前最大面值的硬币个数到0
个，尝试找到一种可行的方案。如果可以找到一种方案，就更新钱数和对应的硬币数量。如果遍历完整个硬币数组仍然无法找到方案，则
说明无法完成找钱操作。
实验6-2 会场安排问题
问题描述：
假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的 。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。)
编程任务：
对于给定的k 个待安排的活动，编程计算使用最少会场的时间表。
数据输入：
由文件input.txt 给出输入数据。第一行有1 个正整数k，表示有k 个待安排的活动。接下来的k 行中，每行有2 个正整数，分别表示k 个待安排的活动开始时间和结束时间。时间以0 点开始的分钟计。
结果输出:
将编程计算出的最少会场数输出到文件output.txt 。
输入文件示例输出文件示例
input.txt output.txt
5 3
1 23
12 28
25 35
27 80
36 50
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 5;
int n, a[N], b[N], ans;
int main() {
// 打开输入文件
freopen("input.txt", "r", stdin);
// 从文件读取输入
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%d%d", &a[i], &b[i]);
sort(a, a + n);
sort(b, b + n);
int j = 0;
ans = 0;
for(int i = 0; i < n; ++i) {
if(a[i] < b[j]) ans++;
else j++;
}
// 打开输出文件
freopen("output.txt", "w", stdout);
// 向文件写入输出
printf("%d", ans);
// 关闭文件
fclose(stdin);
fclose(stdout);
return 0;
}算法具体描述：
1）用数组s和f分别存储各活动的开始时间和结束时间，将s按非递减排序，该次序为各活动选择会场的次序；将f按非递减排序, 由于会场的结束时间由活动的结束时间决定，排序后的数组也是会场的结束时间点。
2）先为最早开始的活动开辟一个会场，此时会场的最早结束时间为该活动的结束时间，然后遍历剩下的活动，对于每个活动，判断当前最早结束的会场内是否仍有活动（即会场的最早结束时间大于该活动的开始时间），如果有，开辟一个新会场；如果没有，说明当前最早结束的会场能容纳当前的活动，更新会场的结束时间点，保证最早结束的会场最先开始下一个活动。
举例
设有4个活动，每个活动的开始和结束时间分别为{1, 6}, {4, 8}, {9, 10}, {7, 18}
实验6-3 文件压缩（Huffman Tree）
【问题描述】给定一个文件，文件由n个字符组成，但他们出现的频度不相同。要求对该文件中的字符集构造哈夫曼树，并计算编码后的文件长度。 【输入形式】
输入的第1行有1个数字n，表示文件中总的字符个数。接下来1行中有n个数字，分别表示n个字符出现的频度。 【输出形式】
输出1行包含1个数字，表示使用哈夫曼编码后该文件的长度。 【样例输入】
5
20 7 10 4 18 【样例输出】
129 【样例说明】
使用哈夫曼编码后，各字符的编码长度分别为2 3 2 3 2，文件长度为220+37+210+34+2*18=129
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,ans;
int num[100100];
priority_queue<int>q;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
int x;
scanf("%d",&x);
q.push(-x);
}
while(q.size()>1)
{
int cur=q.top();
q.pop();
int cur2=q.top();
q.pop();
int sum=cur+cur2;
q.push(sum);
ans+=-sum;
}
printf("%d",ans);
return 0;
}
