《POS机付款.docx》由会员分享，可在线阅读，更多相关《POS机付款.docx（11页珍藏版）》请在三一文库上搜索。
1、精品 料推荐超市 POS 机付款问题一、问题描述超市付款问题超市的自动柜员机（POS机）要找给顾客数量最少的现金。请设计算法解决这种付款优化问题。（提示：试写出用动态规划、贪心法等算法策略来解决该问题，找出多个付款方案、并分析程序运行结果和给出算法的复杂性分析。）二、问题分析超市的自动柜员机（POS 机）要找给顾客数量最少的现金。例如要找4 元 6 角，如果 POS 机送出一大堆硬币，比如46 个 1 角钱，就太麻烦了，而最好找2 个 2 元、 1个 5 角和 1 个 1 角的。动态规划：假定 POS机中有 n 张面值为 Pi 1i n 的货币，用集合 Pp1 , p2 ,., pn 表示，如
2、 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) 是该问题的约束
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.三、算法思想动态规划算法：动态规划法利用问题的最优性原理，以自底向上的方式从子
4、问题的最优解逐步构造出整个问题的最优解。应用动态规划法设计算法一般分为3 个阶段：(1) 分段：将原问题分解成为若干个相互重叠的子问题。(2) 分析：分析问题是否满足最优性原理，找出动态规划函数的递进式。(3) 求解：利用递进式自底向上计算，实现动态规划过程。贪心算法：顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似
5、。可以用贪心法求解的问题中一般具有两个重要的性质：最优子结构性质和贪心选性质 。四、 C+ 源代码动态规划算法 :#include 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,i
6、nt 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)i
7、f(money=0)return;coutselectmoney ;print(money-selectmoney);3精品 料推荐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 选
8、择的钱币面值为：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+;elsei+;coutendl;cout 选择钱币的数量：endl;coutcountendl;void main()int i,money,n,T100;cout 请输入所要找的零钱：money;cout 请输入钱币的种类：n;cout 请输入可找的钱
9、币面值: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);五、时间复杂度分析动态规划算法 :5精品 料推荐该程序的时间复杂度主要取决于冒泡排序和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)=
10、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=money 时，算法的时间复杂度为 T(n)=O(n 2)当 nmoney 时，算法的时间复杂度为 T(n)=O(money*n)贪心算法 :该程序的时间复杂度主要取决于冒泡排序和money_change 函数。void array(int T,int n)int i,j
11、,temp;for(i=1;i=n;i+)/冒泡排序for(j=1;j=n-i;j+)if(Tj=pi)coutpi ;money=money-pi;count+;elsei+;coutendl;cout 选择钱币的数量：endl;coutcountendl;时间复杂度 : T(n)=O(n)所以 :POS 机贪心算法的时间复杂度为T(n)=O(n 2)六、程序运行结果动态规划算法 :7精品 料推荐贪心算法 :8精品 料推荐七、实验数据分析动态规划算法 :程序中不考虑各种面值的钱币数量，每种钱币的数量都有无穷种，可以重复选择同一9精品 料推荐面值的钱币。一、找 5 元零钱：输入： money=
12、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）贪心算法 :程序中不考虑各种面值的钱币数量，每种钱币的数
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精品 料推荐动态规划算法 :一、程
14、序中只能找出整型的零钱，修改数据的类型， 使之能找出浮点型的零钱，如：4 元 6 角。二、程序中各种面值的钱币数量是无限制的，改进算法优化程序从而考虑各种面值的钱币数量。各种钱币输入一次，表示数量为1。 .三、程序中对无法找出零钱的情况未加考虑，修改money_change 函数算法和print函数使无法找出零钱的情况输出“POS 机无法找出零钱” 。贪心算法 :一、程序中对无法找出零钱的情况未加考虑，修改money_change 函数数使无法找出零钱的情况输出“POS 机无法找出零钱” 。二、程序中只能找出整型的零钱，修改数据的类型， 使之能找出浮点型的零钱，如：4 元 6 角。三、程序中各种面值的钱币数量是无限制的，改进算法优化程序从而考虑各种面值的钱币数量。各种钱币输入一次，表示数量为1。四、进一步优化程使算法的时间复杂度降低， 可以去掉冒泡排序， 那么在程序输入钱币面值过程则必须按照递增的顺序输入。11