POS机付款Word格式.docx
《POS机付款Word格式.docx》由会员分享，可在线阅读，更多相关《POS机付款Word格式.docx（14页珍藏版）》请在冰点文库上搜索。
（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<
count[i]）,则选取第i张钱币。
贪心算法：
在POS机付款问题每一步的贪心选择中，在不超过应付款金额的条件下，只选择面值最大的钱币，而不去考虑在后面看来这种选择是否合理，而且它还不会改变决定：
一旦选择了一张钱币，就永远决定。
要尽可能使付出的钱币最快地满足支付要求，其目的是付出的钱币张数慢慢地增加。
在money!
=0的情况下：
如果：
money>
=p[i],则选取第i张钱币，同时money=money-p[i].
否则：
不选取第i张钱币，同时i++,进行下一站钱币的判断。
直到money!
=0.
三、算法思想
动态规划算法：
动态规划法利用问题的最优性原理，以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。
应用动态规划法设计算法一般分为3个阶段：
（1）分段：
将原问题分解成为若干个相互重叠的子问题。
（2）分析：
分析问题是否满足最优性原理，找出动态规划函数的递进式。
（3）求解：
利用递进式自底向上计算，实现动态规划过程。
顾名思义，贪心算法总是作出在当前看来最好的选择。
也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
当然，希望贪心算法得到的最终结果也是整体最优的。
虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。
在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
可以用贪心法求解的问题中一般具有两个重要的性质：
最优子结构性质和贪心选性质。
四、C++源代码
动态规划算法:
#include<
iostream.h>
constintM=100;
constintN=100;
intT[100];
//数组T[]表示存放n种货币递增的面值，money表示所要找的零钱
intcount[M];
//count[i]表示凑合数量为i所需最少的钱币数量,即最优值,则count[i]=min{count[i-T[j]]+1},其中0<
=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;
=M;
i++）
count[i]=0xffff;
count[0]=0;
=money;
{
for（j=0;
=N;
j++）
if（T[j]<
count[i]）
count[i]=count[i-T[j]]+1;
select[i]=T[j];
}
returncount[money];
voidprint（intmoney）
if（money==0）
return;
cout<
<
select[money]<
"
;
print（money-select[money]）;
voidmain（）
inti,money,n;
"
请输入所要找的零钱：
endl;
cin>
>
money;
请输入钱币的种类：
n;
请输入各种钱币面值:
i++）
cin>
T[i];
排序后各种钱币的面值：
array（T,n）;
cout<
T[i]<
------------------------------------pos机找零方案-------------------------------"
POS机找零钱的最优值为：
money_change（money）<
选择的钱币面值为：
print（money）;
}
贪心算法:
#include<
intcount=0;
if（T[j]<
voidmoney_change（intp[],intmoney）
inti=1;
while（money!
=0）
if（money>
=p[i]）
cout<
p[i]<
money=money-p[i];
count++;
else
i++;
选择钱币的数量：
count<
inti,money,n,T[100];
请输入可找的钱币面值:
money_change（T,money）;
五、时间复杂度分析
该程序的时间复杂度主要取决于冒泡排序和money_change函数。
冒泡排序：
for（i=1;
{
if（T[j]>
{
}
时间复杂度：
T（n）=O（n2）
money_change函数：
for（j=0;
T（n）=O（money*n）//money为所找的零钱，n为钱币种类
所以:
当n>
=money时，算法的时间复杂度为T（n）=O（n2）
当n<
money时，算法的时间复杂度为T（n）=O（money*n）
时间复杂度:
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元零钱：
选取面值为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机无法找出零钱”。
二、程序中只能找出整型的零钱，修改数据的类型，使之能找出浮点型的零钱，如：
三、程序中各种面值的钱币数量是无限制的，改进算法优化程序从而考虑各种面值的钱币数量。
四、进一步优化程使算法的时间复杂度降低，可以去掉冒泡排序，那么在程序输入钱币面值过程则必须按照递增的顺序输入。
升级会员 