貪心算法-找零問題-實(shí)驗(yàn)報(bào)告

1、實(shí)驗(yàn)三 課程名稱：算法設(shè)計(jì)與實(shí)現(xiàn) 實(shí)驗(yàn)名稱：貪心算法-找零問題 實(shí)驗(yàn)日期：2019年5月2日 儀器編號(hào)：007 班級(jí)：數(shù)媒0000班姓名：郝仁 學(xué)號(hào) 實(shí)驗(yàn)內(nèi)容假設(shè)零錢系統(tǒng)的幣值是1，p,p2,，pn,p1,且每個(gè)錢幣的重量都等于1，設(shè)計(jì)一個(gè)最壞情況下時(shí)間復(fù)雜度最低的算法，使得對(duì)任何錢數(shù)y，該算法得到的零錢個(gè)數(shù)最少，說明算法的主要設(shè)計(jì)思想，證明它的正確性，并給出最壞情況下的時(shí)間復(fù)雜度。實(shí)驗(yàn)分析引理1（離散數(shù)學(xué)其及應(yīng)用3.1.4）：若n是正整數(shù)，則用25美分、10美分、5美分和1美分等盡可能少的硬幣找出的n美分零錢中，至多有2個(gè)10美分、至多有1個(gè)5美分、至多有4個(gè)1美分硬幣，而不能有2個(gè)10美分

2、和1個(gè)5美分硬幣。用10美分、5美分和1美分硬幣找出的零錢不能超過24美分。證明如果有超過規(guī)定數(shù)目的各種類型的硬幣，就可以用等值的數(shù)目更少的硬幣來替換。注意，如果有3個(gè)10美分硬幣，就可以換成1個(gè)25美分和1個(gè)5美分硬幣；如果有2個(gè)5美分硬幣，就可以換成1個(gè)10美分硬幣；如果有5個(gè)1美分硬幣，就可以換成1個(gè)5美分硬幣；如果有2個(gè)10美分和1個(gè)5美分硬幣，就可以換成1個(gè)25美分硬幣。由于至多可以有2個(gè)10美分、1個(gè)5美分和4個(gè)1美分硬幣，而不能有2個(gè)10美分和1個(gè)5美分硬幣，所以當(dāng)用盡可能少的硬幣找n美分零錢時(shí)，24美分就是用10美分、5美分和1美分硬幣能找出的最大值。假設(shè)存在正整數(shù)n，使得有辦

3、法將25美分、10美分、5美分和1美分硬幣用少于貪心算法所求出的硬幣去找n美分零錢。首先注意，在這種找n美分零錢的最優(yōu)方式中使用25美分硬幣的個(gè)數(shù)q，一定等于貪心算法所用25美分硬幣的個(gè)數(shù)。為說明這一點(diǎn)，注意貪心算法使用盡可能多的25美分硬幣，所以qq。但是q也不能小于q。假如q小于q，需要在這種最優(yōu)方式中用10美分、5美分和1美分硬幣至少找出25美分零錢。而根據(jù)引理1，這是不可能的。由于在找零錢的這兩種方式中一定有同樣多的25美分硬幣，所以在這兩種方式中10美分、5美分和1美分硬幣的總值一定相等，并且這些硬幣的總值不超過24美分。10美分硬幣的個(gè)數(shù)一定相等，因?yàn)樨澬乃惴ㄊ褂帽M可能多的10美分

4、硬幣。而根據(jù)引理1，當(dāng)使用盡可能少的硬幣找零錢時(shí)，至多使用1個(gè)5分硬幣和4個(gè)1分硬幣，所以在找零錢的最優(yōu)方式中也使用盡可能多的10美分硬幣。類似地，5美分硬幣的個(gè)數(shù)相等；最終，1美分的個(gè)數(shù)相等。同上，由于1+p1+p2+p3+.pk-1=pk - 1pk,故當(dāng)n大于pk時(shí)，可以分解為pk與n-pk的值，其中pk只用一個(gè)硬幣值為pk的硬幣就能得到最少硬幣數(shù)，而子問題變成n-pk的最少硬幣數(shù)，依次類推，貪心算法總能得到最好的結(jié)果。假若最優(yōu)解不含幣值的錢幣，即那么存在，如果不是，則與矛盾，不妨設(shè)，那么用1個(gè)幣值為的錢幣替換p個(gè)幣值為的錢幣，總錢幣數(shù)將減少，與這個(gè)解為最優(yōu)解矛盾。下面證明最優(yōu)解簽好含有

5、個(gè)幣值的錢幣。設(shè)錢數(shù)為y時(shí)最優(yōu)解是，則設(shè)其中 通過對(duì)t的歸納不難證明，即最優(yōu)解中含有個(gè)幣值的錢幣。上訴算法在最壞情況下的時(shí)間復(fù)雜度是.實(shí)驗(yàn)源代碼/ 找零ConsoleApplication1.cpp : 此文件包含 main 函數(shù)。程序執(zhí)行將在此處開始并結(jié)束。/數(shù)媒1703班-唐思成/ coin.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。/#includepch.h#include#includeusing namespace std;/money需要找零的錢/coin可用的硬幣的種類/n硬幣種類的數(shù)量void ZhaoLing(int money, int *coin, int n)int *

6、coinNum = new intmoney + 1();/存儲(chǔ)1.money找零最少需要的硬幣的個(gè)數(shù)int *coinValue = new intmoney + 1();/最后加入的硬幣，方便后面輸出是哪幾個(gè)硬幣coinNum0 = 0;for (int i = 1; i = money; i+)int minNum = i;/i面值錢，需要最少硬幣個(gè)數(shù)int usedMoney = 0;/這次找零，在原來的基礎(chǔ)上需要的硬幣for (int j = 0; j = coinj)/找零的錢大于這個(gè)硬幣的面值if (coinNumi - coinj + 1 = minNum & (i = coi

7、nj | coinValuei - coinj != 0)/所需硬幣個(gè)數(shù)減少了minNum = coinNumi - coinj + 1;/更新usedMoney = coinj;/更新coinNumi = minNum;coinValuei = usedMoney;/輸出結(jié)果if (coinValuemoney = 0)cout 找不開零錢 endl;elsecout 需要最少硬幣個(gè)數(shù)為： coinNummoney endl;cout 0)cout coinValuemoney ,;money -= coinValuemoney;cout endl;deletecoinNum;deletecoinValue;int main()int Money;int n,i,p;cout 請(qǐng)輸入需要找零的錢的值 Money;cout 請(qǐng)輸入硬幣種類的數(shù)量 n;int*coin = (int*)malloc(n * sizeof(int);/定義動(dòng)態(tài)長(zhǎng)度的數(shù)組cout 請(qǐng)輸入零錢的底數(shù) p;if (p 0) break;else cout 輸入的數(shù)小于零，請(qǐng)重新輸入 endl;for (i = 0; i n; i+) coini = pow(p,