《算法設(shè)計與分析》實驗三

《算法設(shè)計與分析》

實驗報告三學(xué)生姓名專業(yè)、班級指導(dǎo)教師計算機(jī)與信息工程學(xué)院軟件工程系2014年10月20日實驗三：貪心算法運(yùn)用練習(xí)一、 實驗?zāi)康谋敬螌嶒炇轻槍ω澬乃惴ㄟ\(yùn)用的算法設(shè)計及應(yīng)用練習(xí)，旨在加深學(xué)生對該部分知識點的理解，提高學(xué)生運(yùn)用該部分知識解決問題的能力。二、 實驗步驟與要求實驗前復(fù)習(xí)課程所學(xué)知識以及閱讀和理解指定的課外閱讀材料；學(xué)生獨(dú)自完成實驗指定內(nèi)容；實驗結(jié)束后，用統(tǒng)一的實驗報告模板編寫實驗報告。提交說明：（1） 電子版提交說明：a需要提交Winrar壓縮包，文件名為“《算法設(shè)計與分析》實驗四_學(xué)號_姓名”，如“《算法設(shè)計與分析》實驗四_09290101_張三”。b壓縮包內(nèi)為一個“《算法設(shè)計與分析》實驗四_學(xué)號_姓名”命名的頂層文件夾，其下為兩個文件夾，一個文件夾命名為“源程序”，另一個文件夾命名為“實驗報告電子版”。其下分別放置對應(yīng)實驗成果物。（2） 打印版提交說明：a不可隨意更改模板樣式。b字體：中文為宋體，大小為10號字，英文為TimeNewRoman，大小為10號字。c行間距：單倍行距。（3） 提交截止時間：2014年11月3日16:00。三、 實驗項目傳統(tǒng)的找零錢問題的算法及程序?qū)崿F(xiàn)。特殊的0-1背包問題的求解：本次求解的0-1背包問題的特點為每種物品各有M件，已知每個物品的單位價值，求使得所獲價值最大的裝包方案。四、 實驗過程算法實現(xiàn)程序源代碼（請寫入必要的注釋）。#include<iostream>usingnamespacestd;intmain（）（inta[5]={50,20,10,5,1};〃可以用來找零的錢，以元為單位，不考慮角分intmoney;cout<<"請輸入找零錢數(shù)：”;cin>>money;intb[100];inti=0;intj=0;while(money>0)(if(money>=a[i])(b[j]=a[i];j++;money-=a[i];}elsei++;}cout<<"找回來的零錢："<<'\n';for(intx=0;x<j;x++)cout<<b[x]<<”";cout<<endl;}#include<iostream>usingnamespacestd;voidKANPSACK_DP(intc[50][50],intw[50],intv[50],intn,intC)(for(inti=0;i<=C;i++)(c[0][i]=0;}for(i=1;i<=n;i++)(c[i][0]=0;for(intj=1;j<=C;j++)(if(w[i]<=j)(if(v[i]+c[i-1][j-w[i]]>c[i-1][j])c[i][j]=v[i]+c[i-1][j-w[i]];elsec[i][j]=c[i-1][j];}elsec[i][j]=c[i-1][j];}}}voidOUTPUT_SACK(intc[50][50],intx[50],intw[50],intn,intC)(for(intk=n;k>=2;k--)(if(c[k][C]==c[k-1][C])x[k]=0;else(x[k]=1;C=C-w[k];}}x[1]=c[1][C]?1:0;}intmain()intc[50][50];intw[50],v[50];intx[50];intC,n;cout<<"輸入物品的總個數(shù)：”；cin>>n;cout<<"輸入背包的總?cè)萘浚骸?；cin>>C;cout<<"依次輸入物品的重量："<<endl;for(inti=1;i<=n;i++)(cin>>w[i];}cout<<"依次輸入物品的價值："<<endl;for(i=1;i<=n;i++)(cin>>v[i];}KANPSACK_DP(c,w,v,n,C);OUTPUT_SACK(c,x,w,n,C);cout<<"最優(yōu)解為："<<endl;for(i=1;i<=n;i++)(