您好,欢迎访问三七文档
超市POS机付款问题一、问题描述超市付款问题超市的自动柜员机(POS机)要找给顾客数量最少的现金。请设计算法解决这种付款优化问题。(提示:试写出用动态规划、贪心法等算法策略来解决该问题,找出多个付款方案、并分析程序运行结果和给出算法的复杂性分析。)二、问题分析超市的自动柜员机(POS机)要找给顾客数量最少的现金。例如要找4元6角,如果POS机送出一大堆硬币,比如46个1角钱,就太麻烦了,而最好找2个2元、1个5角和1个1角的。动态规划:假定POS机中有n张面值为niPi1的货币,用集合npppP,...,,21表示,如POS机需支付的现金为A,那么,它必须从P中选取一个最小子集S,使得,spiSmApmii1(1)如果用向量nxxxX,...,,21表示S中所选取的货币,则Sipsipxi10(2)那么,POS机支付的现金必须满足niiiApx1(3)并且niixd1min(4)在上述问题中集合P是该问题的输入,满足式(1)和解称为可行解,式(2)是解的表现形式,因为向量X中有n个元素,每个元素的取值为0或1,所以,可以有n2个不同的向量,所有这些向量的全体构成该问题的解空间,式(3)是该问题的约束条件,式(4)是该问题的目标函数,使式(4)取得极小值的解称为该问题的最优解。对POS机付款问题:(1)count[i]表示凑合数量为i所需最少的钱币数量,即最优值。(2)则count[i]=min{count[i-T[j]]+1}(原问题分段)。(3)其中0=j=N-1动态规划函数的递进式。(4)满足(T[j]=i&&count[i-T[j]]+1count[i]),则选取第i张钱币。贪心算法:在POS机付款问题每一步的贪心选择中,在不超过应付款金额的条件下,只选择面值最大的钱币,而不去考虑在后面看来这种选择是否合理,而且它还不会改变决定:一旦选择了一张钱币,就永远决定。要尽可能使付出的钱币最快地满足支付要求,其目的是付出的钱币张数慢慢地增加。在money!=0的情况下:如果:money=p[i],则选取第i张钱币,同时money=money-p[i].否则:不选取第i张钱币,同时i++,进行下一站钱币的判断。直到money!=0.三、算法思想动态规划算法:动态规划法利用问题的最优性原理,以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。应用动态规划法设计算法一般分为3个阶段:(1)分段:将原问题分解成为若干个相互重叠的子问题。(2)分析:分析问题是否满足最优性原理,找出动态规划函数的递进式。(3)求解:利用递进式自底向上计算,实现动态规划过程。贪心算法:顾名思义,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。当然,希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。可以用贪心法求解的问题中一般具有两个重要的性质:最优子结构性质和贪心选性质。四、C++源代码动态规划算法:#includeiostream.hconstintM=100;constintN=100;intT[100];//数组T[]表示存放n种货币递增的面值,money表示所要找的零钱intcount[M];//count[i]表示凑合数量为i所需最少的钱币数量,即最优值,则count[i]=min{count[i-T[j]]+1},其中0=j=N-1intselect[M];//每个表示count[i]在取最小值时的选择,即上式中的jvoidarray(intT[],intn){inti,j,temp;for(i=1;i=n;i++)//冒泡排序{for(j=1;j=n-i;j++){if(T[j]T[j+1]){temp=T[j];T[j]=T[j+1];T[j+1]=temp;}}}}intmoney_change(intmoney){inti=0;intj=0;for(i=0;i=M;i++)count[i]=0xffff;count[0]=0;for(i=0;i=money;i++){for(j=0;j=N;j++)if(T[j]=i&&count[i-T[j]]+1count[i]){count[i]=count[i-T[j]]+1;select[i]=T[j];}}returncount[money];}voidprint(intmoney){if(money==0)return;coutselect[money];print(money-select[money]);}voidmain(){inti,money,n;cout请输入所要找的零钱:endl;cinmoney;cout请输入钱币的种类:endl;cinn;cout请输入各种钱币面值:endl;for(i=1;i=n;i++)cinT[i];cout排序后各种钱币的面值:endl;array(T,n);for(i=1;i=n;i++)coutT[i];coutendl;cout------------------------------------pos机找零方案-------------------------------endl;coutPOS机找零钱的最优值为:endl;coutmoney_change(money)endl;cout选择的钱币面值为:endl;print(money);coutendl;}贪心算法:#includeiostream.hintcount=0;voidarray(intT[],intn){inti,j,temp;for(i=1;i=n;i++)//冒泡排序{for(j=1;j=n-i;j++){if(T[j]T[j+1]){temp=T[j];T[j]=T[j+1];T[j+1]=temp;}}}}voidmoney_change(intp[],intmoney){inti=1;while(money!=0){if(money=p[i]){coutp[i];money=money-p[i];count++;}elsei++;}coutendl;cout选择钱币的数量:endl;coutcountendl;}voidmain(){inti,money,n,T[100];cout请输入所要找的零钱:endl;cinmoney;cout请输入钱币的种类:endl;cinn;cout请输入可找的钱币面值:endl;for(i=1;i=n;i++){cinT[i];}cout排序后各种钱币的面值:endl;array(T,n);for(i=1;i=n;i++)coutT[i];coutendl;cout------------------------------------pos机找零方案-------------------------------endl;cout选择的钱币面值为:endl;money_change(T,money);}五、时间复杂度分析动态规划算法:该程序的时间复杂度主要取决于冒泡排序和money_change函数。冒泡排序:voidarray(intT[],intn){for(i=1;i=n;i++){for(j=1;j=n-i;j++){if(T[j]T[j+1]){temp=T[j];T[j]=T[j+1];T[j+1]=temp;}}}}时间复杂度:T(n)=O(n2)money_change函数:intmoney_change(intmoney){inti=0;intj=0;for(i=0;i=M;i++)count[i]=0xffff;count[0]=0;for(i=0;i=money;i++){for(j=0;j=n;j++)if(T[j]=i&&count[i-T[j]]+1count[i]){count[i]=count[i-T[j]]+1;select[i]=T[j];}}returncount[money];}时间复杂度:T(n)=O(money*n)//money为所找的零钱,n为钱币种类所以:当n=money时,算法的时间复杂度为T(n)=O(n2)当nmoney时,算法的时间复杂度为T(n)=O(money*n)贪心算法:该程序的时间复杂度主要取决于冒泡排序和money_change函数。voidarray(intT[],intn){inti,j,temp;for(i=1;i=n;i++)//冒泡排序{for(j=1;j=n-i;j++){if(T[j]T[j+1]){temp=T[j];T[j]=T[j+1];T[j+1]=temp;}}}}时间复杂度:T(n)=O(n2)voidmoney_change(intp[],intmoney){inti=1;while(money!=0){if(money=p[i]){coutp[i];money=money-p[i];count++;}elsei++;}coutendl;cout选择钱币的数量:endl;coutcountendl;}时间复杂度:T(n)=O(n)所以:POS机贪心算法的时间复杂度为T(n)=O(n2)六、程序运行结果动态规划算法:贪心算法:七、实验数据分析动态规划算法:程序中不考虑各种面值的钱币数量,每种钱币的数量都有无穷种,可以重复选择同一面值的钱币。一、找5元零钱:输入:money=5;//所要找的零钱T[3]={1,5,10};//钱币的面值输出:选取面值为5元的钱币一张(最优值为1,钱币面值为5)二、找10元零钱:输入:money=10;//所要找的零钱T[5]={1,3,4,6,8};//钱币的面值输出:选取面值为4元的钱币一张和面值为6的面值一张(最优值为2,钱币面值为4,6)三、找97元零钱:输入:money=97;//所要找的零钱T[4]={1,9,5,13};//钱币的面值输出:选取面值为1元的钱币一张,面值为5元的钱币一张和面值为13元的钱币7张(最优值为9,钱币面值为1,5,13)贪心算法:程序中不考虑各种面值的钱币数量,每种钱币的数量都有无穷种,可以重复选择同一面值的钱币。一、找0元零钱:输入:money=0;//所要找的零钱T[3]={5,10,3,8};//钱币的面值输出:不选取任何面值的钱币(钱币为为0,钱币面值无)二、找10元零钱:输入:money=10;//所要找的零钱T[5]={1,3,4,6,8};//钱币的面值输出:选取面值为8元的钱币一张和面值为1的面值2张(钱币为2,钱币面值为8,1)三、找100元零钱:输入:money=100;//所要找的零钱T[3]={5,1,2}//钱币的面值输出:选取面值为5元的钱币20张(钱币数量为9,钱币面值为5)八、程序改进方向动态规划算法:一、程序中只能找出整型的零钱,修改数据的类型,使之能找出浮点型的零钱,如:4元6角。二、程序中各种面值的钱币数量是无限制的,改进算法优化程序从而考虑各种面值的钱币数量。各种钱币输入一次,表示数量为1。.三、程序中对无法找出零钱的情况未加考虑,修改money_change函数算法和print函数使无法找出零钱的情况输出“POS机无法找出零钱”。贪心算法:一、程序中对无法找出零钱的情况未加考虑,修改money_change函数数使无法找出零钱的情况输出“POS机无法找出零钱”。二、程序中只能找出整型的零钱,修改数据的类型,使之能找出浮点
本文标题:POS机付款
链接地址:https://www.777doc.com/doc-1171478 .html