POS机付款.docx

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