None

(连续邮资问题)某国发行了 n 种不同面值的邮票,并规定每封信最多允许贴 m 张邮票,在这 些约束下,为了能贴出 {1 , 2,3, …,maxvalue} 连续整数集合的所有邮资,并使 maxvalue 的值最 大,应该如何设计各邮票的面值?例如,当 n=5 、m=4 时,面值设计为 {1 , 3,11 ,15 ,32} ,可使 maxvalue 达到最大值 70 (或者说,用这些面值的 1 至4 张邮票可以表示不超过 70 的所有邮资,但无 法表示邮资 71 。而用其他面值的 1 至4 张邮票如果可以表示不超过 k 的所有邮资,必有 k ≤70 )。


 下面是用递归回溯求解连续邮资问题的程序。数组 x[1:n] 表示 n 种不同的邮票面值,并约定各元 素按下标是严格递增的。数组 bestx[1:n] 存放使 maxvalue 达到最大值的邮票面值(最优解), 数组 y[maxl] 用于记录当前已选定的邮票面值 x[1:i] 能贴出的各种邮资所需的最少邮票张数。请将程 序补充完整。


赣ICP备20007335号-2