POS机付款

超市POS机付款问题一、问题描述超市付款问题超市的自动柜员机（POS机）要找给顾客数量最少的现金。请设计算法解决这种付款优化问题。（提示：试写出用动态规划、贪心法等算法策略来解决该问题，找出多个付款方案、并分析程序运行结果和给出算法的复杂性分析。）二、问题分析超市的自动柜员机（POS机）要找给顾客数量最少的现金。例如要找4元6角，如果POS机送出一大堆硬币，比如46个1角钱，就太麻烦了，而最好找2个2元、1个5角和1个1角的。动态规划：假定POS机中有n张面值为的货币，用集合表示，如POS机需支付的现金为A，那么，它必须从P中选取一个最小子集S，使得 (1)如果用向量表示S中所选取的货币,则 (2)那么,POS机支付的现金必须满足 (3)并且 (4)在上述问题中集合P是该问题的输入,满足式(1)和解称为可行解,式(2)是解的表现形式,因为向量X中有n 个元素,每个元素的取值为0或1,所以,可以有个不同的向量,所有这些向量的全体构成该问题的解空间,式(3)是该问题的约束条件,式(4)是该问题的目标函数,使式(4)取得极小值的解称为该问题的最优解。对POS机付款问题：(1)counti表示凑合数量为i所需最少的钱币数量,即最优值。(2)则counti=mincounti-Tj+1(原问题分段)。(3)其中0=j=N-1动态规划函数的递进式。(4)满足(Tj= i&counti-Tj+1=pi,则选取第i张钱币，同时money=money-pi.否则： 不选取第i张钱币，同时i+,进行下一站钱币的判断。直到money!=0.三、算法思想动态规划算法：动态规划法利用问题的最优性原理，以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。应用动态规划法设计算法一般分为3个阶段：(1)分段：将原问题分解成为若干个相互重叠的子问题。(2)分析：分析问题是否满足最优性原理，找出动态规划函数的递进式。(3)求解：利用递进式自底向上计算，实现动态规划过程。贪心算法：顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。可以用贪心法求解的问题中一般具有两个重要的性质：最优子结构性质和贪心选性质。四、C+源代码动态规划算法:#include const int M=100; const int N=100; int T100; / 数组T表示存放n种货币递增的面值，money表示所要找的零钱 int countM;/counti表示凑合数量为i所需最少的钱币数量,即最优值,则counti=mincounti-Tj+1,其中0=j=N-1 int selectM;/每个表示counti在取最小值时的选择，即上式中的j void array(int T,int n)int i,j,temp;for(i=1;i=n;i+)/冒泡排序for(j=1;jTj+1)temp=Tj;Tj=Tj+1;Tj+1=temp; int money_change(int money) int i = 0; int j = 0; for(i=0;i=M;i+) counti=0xffff; count0 = 0; for(i=0;i=money;i+) for(j=0;j=N;j+) if(Tj= i&counti-Tj+1counti) counti = counti-Tj+1; selecti = Tj; return countmoney; void print(int money) if(money=0) return; coutselectmoney ; print(money-selectmoney); void main()int i,money,n;cout请输入所要找的零钱：money;cout请输入钱币的种类：n;cout请输入各种钱币面值:endl;for(i=1;iTi;cout排序后各种钱币的面值：endl;array(T,n); for(i=1;i=n;i+)coutTi ;coutendl;cout-pos机找零方案-endl; coutPOS机找零钱的最优值为：endl; coutmoney_change(money)endl; cout选择的钱币面值为：endl;print(money); coutendl;贪心算法:#includeint count=0;void array(int T,int n)int i,j,temp;for(i=1;i=n;i+)/冒泡排序for(j=1;j=n-i;j+)if(Tj=pi) coutpi ; money=money-pi; count+; else i+; coutendl; cout选择钱币的数量：endl;coutcountendl;void main() int i,money,n,T100;cout请输入所要找的零钱：money;cout请输入钱币的种类：n; cout请输入可找的钱币面值:endl; for(i=1;iTi; cout排序后各种钱币的面值：endl;array(T,n); for(i=1;i=n;i+)coutTi ;coutendl; cout-pos机找零方案-endl;cout选择的钱币面值为：endl; money_change(T,money);五、时间复杂度分析动态规划算法:该程序的时间复杂度主要取决于冒泡排序和money_change函数。冒泡排序：void array(int T,int n)for(i=1;i=n;i+) for(j=1;jTj+1) temp=Tj;Tj=Tj+1;Tj+1=temp; 时间复杂度：T(n)=O(n2)money_change函数：int money_change(int money) int i = 0; int j = 0; for(i=0;i=M;i+) counti=0xffff; count0 = 0; for(i=0;i=money;i+) for(j=0;j=n;j+) if(Tj= i&counti-Tj+1=money时，算法的时间复杂度为T(n)=O(n2) 当nmoney时，算法的时间复杂度为T(n)=O(money*n)贪心算法:该程序的时间复杂度主要取决于冒泡排序和money_change函数。void array(int T,int n)int i,j,temp;for(i=1;i=n;i+)/冒泡排序for(j=1;j=n-i;j+)if(Tj=pi) coutpi ; money=money-pi; count+; else i+; coutendl; cout选择钱币的数量：endl;coutcountendl; 时间复杂度: T(n)=O(n)所以: POS机贪心算法的时间复杂度为T(n)=O(n2)六、程序运行结果动态规划算法: 贪心算法:七、实验数据分析动态规划算法:程序中不考虑各种面值的钱币数量，每种钱币的数量都有无穷种，可以重复选择同一面值的钱币。一、找5元零钱：输入：money=5；/所要找的零钱T3=1,5,10;/钱币的面值 输出： 选取面值为5元的钱币一张（最优值为1，钱币面值为5） 二、找10元零钱： 输入：money=10;/所要找的零钱 T5=1,3,4,6,8;/钱币的面值 输出： 选取面值为4元的钱币一张和面值为6的面值一张（最优值为2，钱币面值为4,6） 三、找97元零钱： 输入： money=97；/所要找的零钱 T4=1,9,5,13;/钱币的面值 输出： 选取面值为1元的钱币一张，面值为5元的钱币一张和面值为13元的钱币7张（最优值为9，钱币面值为1,5,13）贪心算法:程序中不考虑各种面值的钱币数量，每种钱币的数量都有无穷种，可以重复选择同一面值的钱币。一、找0元零钱：输入：money=0；/所要找的零钱T3=5,10,3,8;/钱币的面值输出： 不选取任何面值的钱币（钱币为为0，钱币面值无）二、找10元零钱： 输入：money=10;/所要找的零钱 T5=1,3,4,6,8;/钱币的面值 输出： 选取面值为8元的钱币一张和面值为1的面值2张（钱币为2，钱币面值为8,1）三、找100元零钱： 输入： money=100；/所要找的零钱 T3=5,1,2/钱币的面值 输出： 选取面值为5元的钱币20张（钱币数量为9，钱币面值为5）八、程序改进方向动态规划算法: 一、程序中只能找出整型的零钱，修改数据的类型，使之能找出浮点型的零钱，如：4元6角。 二、程序中各种面值的钱币数量是无限制的，改进算法优化程序从而考虑各种面值的钱币数量。各种钱币输入一次，表示数量为1。. 三、程序中对无法找出零钱的情况未加考虑，修改money_change函数算法和print函数使无法找出零钱的情况输出“POS机无法找出零钱”。 贪心算法:一、程序中对无法找出零钱的情况未加