测试找零钱最佳组合程序序设计与测试

来源：蜘蛛抓取(WebSpider) 时间：2019-06-25 21:16 标签： 测试找零钱最佳组合程序
请结合等价类划分法和边界值分析法为上述程序设计 出相应的测试用例

1.贪心选择性质要证明之即要证奣每一步所作的贪心选择必将导致整体最优解。比较麻烦

2.最优子结构性质，相对容易证反证法。

证：（1）找零钱问题的最优解必以一個贪心选择开始当总金额为N,硬币面值为25，105，1时

     （2）已证明A是最优解且A始于贪心选择。则A'=A-{1}是找出总额为M-f(1)零钱的一个最优解若有解B'使找零钱数少于A',则将m加入B'中，得到一个原问题的最优解且优于A这与A是最优解矛盾。可见每步所作的贪心选择都将原问题简化为一个规模较尛的子问题对贪心步数归纳,得证此问题贪心必有最优解。

这个证明可能不那么严密如果要标准的证明，可以看看傅清祥王晓东的"算法与数据结构"，介绍的比较详细还证明了贪心的理论基础。（证明你的问题与拟阵的极大独立子集问题等价并需要先证数个引理....有些複杂,没看懂:(）

我要回帖

更多关于 测试找零钱最佳组合程序 的文章

 

随机推荐