算法设计与实践 找钱，宿营天数实验报告

4.7假设零钱系统的币值是{1，p,p^2,……，p^n},p>1,且每个钱币的重量都等于1，设计一个最坏情况下时间复杂度最低的算法，使得对任何钱数y，该算法得到的零钱个数最少，说明算法的主要设计思想，证明它的正确性，并给出最坏情况下的时间复杂度。 4.8考察路线上有n个地点可以作为宿营地。一直宿营地到出发点的距离依次为x1,x2,……，xn,且满足x1<x2<……<xn,每天他们只能前进30千米，而任意两个相邻的宿营地之间的距离不超过30千米，在每个宿营地只住1天，他们希望找到一个行动计划，使得总的宿营天数达到最少，求解这个问题。