题目内容
（请给出正确答案）
[主观题]
假设零钱系统的币值是[图]. 且每个钱币的重量都等于1....
假设零钱系统的币值是![假设零钱系统的币值是[图]. 且每个钱币的重量都等于1....假设零钱系统的币值是. 且每个钱币的重](http://static.jiandati.com/83a0424-chaoxing2016-1080032.png)
. 且每个钱币的重量都等于1. 设计一个最坏情况下时间复杂度最低的算法，使得对任何钱数y，该算法得到的零钱个数最少. 说明算法的主要设计思想，证明它的正确性，并给出最坏情况下的时间复杂度.
提问人：网友flyfishy
发布时间：2022-01-07
如搜索结果不匹配，请 
设有n中不同面值的硬币，第i种硬币的币值是
，其中
，重量是
，i=1, 2, ..., n且现在购买总价值为y的某些商品，需要用这些硬币付款，如果每种钱币使用的个数不限，问如何选择付款的方法使得付出钱币的总重量最轻？设计一个求解该问题的算法，给出算法的伪代码描述并分析算法的时间复杂度，假设问题的输入实例是：
给出算法在该实例上计算的备忘录和标记函数表，并说明付款的方法。
和总钱数M都是正整数，如果每种币值的钱币至多使用1次，问：对于M是否可以有一种找零钱的方法？设计一个算法求解上述问题，说明算法的设计思想，分析算法最坏情况下的时间复杂度。
及
时，函数
的极限都存在且都等于
，则
及
时,函数
的极限都存在且都等于A是
的()条件。
