POS机付款.docx

POS机付款.docx

《POS机付款.docx》由会员分享，可在线阅读，更多相关《POS机付款.docx（14页珍藏版）》请在冰点文库上搜索。

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）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]]+1

贪心算法：

在POS机付款问题每一步的贪心选择中，在不超过应付款金额的条件下，只选择面值最大的钱币，而不去考虑在后面看来这种选择是否合理，而且它还不会改变决定：

一旦选择了一张钱币，就永远决定。

要尽可能使付出的钱币最快地满足支付要求，其目的是付出的钱币张数慢慢地增加。

在money!

=0的情况下：

如果：

money>=p[i],则选取第i张钱币，同时money=money-p[i].

否则：

不选取第i张钱币，同时i++,进行下一站钱币的判断。

直到money!

=0.

三、算法思想

动态规划算法：

动态规划法利用问题的最优性原理，以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。

应用动态规划法设计算法一般分为3个阶段：

（1）分段：

将原问题分解成为若干个相互重叠的子问题。

（2）分析：

分析问题是否满足最优性原理，找出动态规划函数的递进式。

（3）求解：

利用递进式自底向上计算，实现动态规划过程。

贪心算法：

顾名思义，贪心算法总是作出在当前看来最好的选择。

也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。

当然，希望贪心算法得到的最终结果也是整体最优的。

虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。

在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

可以用贪心法求解的问题中一般具有两个重要的性质：

最优子结构性质和贪心选性质。

四、C++源代码

动态规划算法:

#include

constintM=100;

constintN=100;

intT[100];//数组T[]表示存放n种货币递增的面值，money表示所要找的零钱

intcount[M];//count[i]表示凑合数量为i所需最少的钱币数量,即最优值,则count[i]=min{count[i-T[j]]+1},其中0<=j<=N-1

intselect[M];//每个表示count[i]在取最小值时的选择，即上式中的j

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;

}

}

}

}

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]]+1

{

count[i]=count[i-T[j]]+1;

select[i]=T[j];

}

}

returncount[money];

}

voidprint（intmoney）

{

if（money==0）

return;

cout<

print（money-select[money]）;

}

voidmain（）

{

inti,money,n;

cout<<"请输入所要找的零钱：

"<

cin>>money;

cout<<"请输入钱币的种类：

"<

cin>>n;

cout<<"请输入各种钱币面值:

"<

for（i=1;i<=n;i++）

cin>>T[i];

cout<<"排序后各种钱币的面值：

"<

array（T,n）;

for（i=1;i<=n;i++）

cout<

cout<

cout<<"------------------------------------pos机找零方案-------------------------------"<

cout<<"POS机找零钱的最优值为：

"<

cout<

cout<<"选择的钱币面值为：

"<

print（money）;

cout<

}

贪心算法:

#include

intcount=0;

voidarray（intT[],intn）

{

inti,j,temp;

for（i=1;i<=n;i++）//冒泡排序

{

for（j=1;j<=n-i;j++）

{

if（T[j]

{

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]）

{

cout<

money=money-p[i];

count++;

}

else

i++;

}

cout<

cout<<"选择钱币的数量：

"<

cout<

}

voidmain（）

{

inti,money,n,T[100];

cout<<"请输入所要找的零钱：

"<

cin>>money;

cout<<"请输入钱币的种类：

"<

cin>>n;

cout<<"请输入可找的钱币面值:

"<

for（i=1;i<=n;i++）

{

cin>>T[i];

}

cout<<"排序后各种钱币的面值：

"<

array（T,n）;

for（i=1;i<=n;i++）

cout<

cout<

cout<<"------------------------------------pos机找零方案-------------------------------"<

cout<<"选择的钱币面值为：

"<

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]]+1

{

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）

当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]

{

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]）

{

cout<

money=money-p[i];

count++;

}

else

i++;

}

cout<

cout<<"选择钱币的数量：

"<

cout<

}

时间复杂度:

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机无法找出零钱”。

二、程序中只能找出整型的零钱，修改数据的类型，使之能找出浮点型的零钱，如：

4元6角。

三、程序中各种面值的钱币数量是无限制的，改进算法优化程序从而考虑各种面值的钱币数量。

各种钱币输入一次，表示数量为1。

四、进一步优化程使算法的时间复杂度降低，可以去掉冒泡排序，那么在程序输入钱币面值过程则必须按照递增的顺序输入。