公司有一个比较坑爹的报销方案，需要根据一堆零碎的发票中，凑出一个目标金额，要求误差在1块钱以内。
例如：你有一堆发票[100, 101, 103, 105, 106, 132, 129, 292, 182, 188, 224.3, 40.5, 35.9, 32.5, 39, 12, 17.5, 28, 35, 34, 26.32, 28, 35, 39, 25, 1, 24, 35, 45, 47, 32.11, 45, 32, 38.88, 44, 36.5, 35.8, 45, 26.5, 33, 25, 364, 27.3, 39.2, 180, 279, 282, 281, 285, 275, 277, 278, 200, 201, 1959.12, 929.53, 1037.03, 1033.9]，让你从这堆票中凑出5000块来，然后最多不能超过1块钱。你瞧瞧这是人干的事么！
缺点：每次人肉去对比，浪费大量的时间。
操作过程大概是这样的：新建一个excel表格，将所有的金额录入，然后自己勾选发票，直到目标金额出现，如下图
人品大爆发的时候一下就凑出来，运气不好的时候凑着凑着一两个小时就过去了！
因此，我们急需一个程序自己去干这个事。
最差方案：全组和
使用全组合，搜索所有组合方案，遍历满足的结果输出，时间复杂度为O(n!)，原先调用了python的排列组合函数实现，结果卡得不行，有时候能把程序跑挂了
中等方案：回溯暴力破解
利用回溯输出，存在重复递归，时间复杂度为O(2^n)，一般来说已经满足正常需求，但是如果n很大，还是影响性能
最优方案：动态规划
时间复杂度为O(n*w)，为最快方案，提升气质指数，5颗星！
最终用动态规划思想实现，空间换时间，200个碎票匹配1万的金额秒出结果，大概使用800M内存，
代码已经贴到github：chenqionghe/amount-calculator
核心代码如下
四、使用方式1.直接调用代码（适合用来开发自己的软件）
运行结果
耗时97毫秒，共计算出577种方案，性能高到令人忍不住想鼓掌！
这种方式适合在自己开发的程序中使用，比如要出一个web界面，给前端提供数据
2.命令行模式（适合不会编程的人使用）
这种方式适合不会go语言，或者不会编程的人使用，只需编译出对应平台的版本就行。
一次编译多次分发，相当于copy了个绿色版软件到电脑上直接使用
编译过程如下
- 新建一个go文件：main.go
- 编译
- 运行该工具
可以看到，命令行直接输出了所有匹配的组合，还给出了每个组合的金额，对于使用者来说，不会编程语言也完全没有关系，只需要自己执行一下即可，相当方便。
另外，命令行模式省了一个编译的过程，效率更高，推荐！
五、总结技术解放生产力，这种重复且费时的劳动完全应该由程序去做，可惜的是
- 一般的产品提不出这样的需求
- 产品即使能提这样的需求，开发也不一定能实现出来
- 开发即使能实现出来，程序也不一定能跑得动，因为很可能太耗内存或太耗CPU，还没等结果运行出来程序就挂了
哈哈，稍微有点吹牛逼了，不管怎么样，就一句话：yeah buddy! light weight baby! 让我听到你们的尖叫声！