实验三
课程名称：算法设计与实现实验名称：贪心算法-找零问题
实验日期：2019年5月2日仪器编号：007
班级：数媒0000班姓名：郝仁学号0000000000
实验内容
假设零钱系统的币值是{1，p,p^2,……，p^n},p>1,且每个钱币的重量都等于1，设计一个最坏情况下时间复杂度最低的算法，使得对任何钱数y，该算法得到的零钱个数最少，说明算法的主要设计思想，证明它的正确性，并给出最坏情况下的时间复杂度。

实验分析
引理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美分的个数相等。

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

假若最优解不含币值j
p 的钱币，即112210--+⋯+++=j j p x p x p x x y 那么存在{}1,1,0,-⋯∈≥j i p x i ，，如果不是，则
11)(1(12112210-=+⋯+++-≤+⋯+++=---j j j j p p p p p p x p x p x x y
与j p ≥y 矛盾，不妨设p x i ≥，那么用1个币值为1+i p 的钱币替换p 个币值为j
p 的钱币，总钱币数将减少1-p ，与这个解为最优解矛盾。

下面证明最优解签好含有⎣⎦
j p /y 个币值j p 的钱币。

设钱数为y 时最优解是()y F j ，则
()()
()⎪⎩⎪⎨⎧<≥+-=-j j j j j j p y y F p y p y F y F 11 设()j j p tp y <+=δδ其中⎣⎦j
p y t /= 通过对t 的归纳不难证明()()δ1
j -+=j F t y F ，即最优解中含有⎣⎦
j p y /个币值j p 的钱币。

上诉算法在最坏情况下的时间复杂度是()()}log ,m in{y n O n W =.
实验源代码
// 找零ConsoleApplication1.cpp : 此文件包含 "main" 函数。

程序执行将在此处开始并结束。

//数媒1703班-1191170329-唐思成
// coin.cpp : 定义控制台应用程序的入口点。

//
#include "pch.h"
#include <iostream>
#include <math.h>
using namespace std;
//money 需要找零的钱
//coin 可用的硬币的种类
//n 硬币种类的数量
void ZhaoLing(int money , int *coin , int n ){
int *coinNum = new int [money + 1]();//存储1...money 找零最少需要的硬币的个数
int *coinValue = new int [money + 1]();//最后加入的硬币，方便后面输出是哪几个硬币 coinNum[0] = 0;
for (int i = 1; i <= money; i++)
{
int minNum = i;//i面值钱，需要最少硬币个数
int usedMoney = 0;//这次找零，在原来的基础上需要的硬币
for (int j = 0; j < n; j++)
{
if (i >= coin[j])//找零的钱大于这个硬币的面值
{
if (coinNum[i - coin[j]] + 1 <= minNum && (i == coin[j] || coinValue[i - coin[j]] != 0))//所需硬币个数减少了
{
minNum = coinNum[i - coin[j]] + 1;//更新
usedMoney = coin[j];//更新
}
}
}
coinNum[i] = minNum;
coinValue[i] = usedMoney;
}
//输出结果
if (coinValue[money] == 0)
cout <<"找不开零钱"<< endl;
else
{
cout <<"需要最少硬币个数为："<< coinNum[money] << endl;
cout <<"硬币分别为:";
while (money > 0)
{
cout << coinValue[money] <<",";
money -= coinValue[money];
}
cout << endl;
}
delete[]coinNum;
delete[]coinValue;
}
int main(){
int Money;
int n,i,p;
cout <<"请输入需要找零的钱的值"<< endl;
cin >> Money;
cout <<"请输入硬币种类的数量"<< endl;
cin >> n;
int*coin = (int*)malloc(n * sizeof(int));//定义动态长度的数组
cout <<"请输入零钱的底数"<< endl;
while(1) {
cin >> p;
if (p > 0) {
break;
}
else {
cout <<"输入的数小于零，请重新输入"<< endl;
}
}
for (i = 0; i < n; i++) {
coin[i] = pow(p, i);
}
cout <<"找零系统中的零钱种类为："<< endl;
for (i = 0; i < n; i++) {
cout << coin[i] <<",";
}
cout << endl;
ZhaoLing(Money, coin, n);
system("pause");
return 0;
}
实验结果。