文档介绍：超市POS机付款问题
一、问题描述
超市付款问题
超市的自动柜员机（posM）要找给顾客数量最少的现金。请设计算法解决这种付款优化问题。
（提示：试写出用动态规划、贪心法等算法策略来解决该问题，找出多个付款方案、并分析程序运行结果和给出算法的复杂性分析。）
二、问题分析
超市的自动柜员机（POS机）要找给顾客数量最少的现金。例如要找 4元6角，如果POS机送出一大堆硬币，比如 46个1角钱，就太麻烦了，而最好找 2个2元、1 个5角和1个1角的。
动态规划：
假定POS机中有n张面值为R 1 i n的货币，用集合P p1,p2,...,pn表
示，如POSM需支付的现金为 A,那么，它必须从 P中选取一个最小子集 S,使得
Pi s,
m
pi A m
i 1
S
⑴
如果用向量 X X1,X2,...,Xn
表示S中所选取的货币
，则
1 Pi S
⑵
⑶
(4)
X i 0 Pi s
那么,POS机支付的现金必须满足
n
Xi Pi A
i 1
并且
n
d min xi
在上述问题中集合 P是该问题的输入，满足式（1）和解称为可行解，式（2）是解
的表现形式，因为向量X中有n个元素，每个元素的取值为 0或1,所以，可以有2n
个不同的向量，所有这些向量的全体构成该问题的解空间，式(3)是该问题的约束条
件，式(4)是该问题的目标函数,使式(4)取得极小值的解称为该问题的最优解。
对POSM付款问题：
⑴count[i]表示凑合数量为i所需最少的钱币数量，即最优值。
⑵则 count[i]=min{count[i-T[j]]+1} (原问题分段)。
⑶其中0<=j<=N-1动态规划函数的递进式。
(4)满足(T[j]<= i&&count[i-T[j]]+1<count[i])，则选取第 i 张钱币。
贪心算法:
在posM付款问题每一步的贪心选择中，在不超过应付款金额的条件下，只选择面值最大的钱币，而不去考虑在后面看来这种选择是否合理，而且它还不会改变决定:
一旦选择了一张钱币，就永远决定。要尽可能使付出的钱币最快地满足支付要求，其目的是付出的钱币张数慢慢地增加。
在money!=0的情况下：
如果： money>=p[i]，则选取第i张钱币，同时 money=money-p[i].
否则：不选取第i张钱币，同时i++ ,进行下一站钱币的判断。直到 money!=0.
二、算法思想
动态规划算法:
动态规划法利用问题的最优性原理，以自底向上的方式从子问题的最优解逐步构造
出整个问题的最优解。应用动态规划法设计算法一般分为 3个阶段：
分段：将原问题分解成为若干个相互重叠的子问题。
分析：分析问题是否满足最优性原理，找出动态规划函数的递进式。
求解：利用递进式自底向上计算，实现动态规划过程。
贪心算法:
C++源代码
四、C++源代码
顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。在一些情况下