Question

pascal中的题

设有已知面额的邮票m种，每种有n张，问：用总数不超过n张的邮票进行组合，能组合的邮票面额中可以连续出现面额数最多有多少？ n=4，m=3，面额为1,2,4，最后结果是14，怎么算出来的啊，这个题什么意思啊
急急急，求助

Answer 1

这个题目的意思就是：有m种邮票，每种邮票有n张，一共就有m*n张邮票，从中选出不超过n张，把面值求和，这样可以得到很多结果，这些结果中有的是连续的，如：3,4,5,6；全部结果中有部分是断的，如3,4,5,6,8,9。最后要你输出的是这些结果中最长不断的连续数有多长。
如例题数据最长有14个结果是连续的。
这个题可以用递推，也可以dfs爆搜（这个套路固定就略了）。

因为每种邮票有n张，一共只能使用n张，所以只要控制获得某个面值和的前提是使用了不超过n张邮票就绝对不会有任何一种邮票的使用张数超过已经给出的可用数量。

递推的话，可以这么做：
伪代码如下：
min 结果下限
max 结果上限
f[] 整型组 记录获得该面值时使用的邮票张数
v[] 整型组 读入面额

初始化 f[] 为 false
初始化 f[0] 为 true
for i = min to max begin 从下限到上限遍历
for j = 1 to m 遍历各种面额的邮票
if f[i-v[j]]<n then 总张数不大于n，即总张数-1小于n，就可能是合理结果
if f[i]=0 then f[i] = f[i-v[j]] + 1 若这是第一个合理结果直接记录
else f[i] = min{ f[i] , f[i-v[j]] + 1 } 若不是第一个合理结果，选择更优的结果
end
result = 0 从这里开始是寻找最后的结果
plus = 0
for i = min to max
if f[i] then inc(plus)
else begin
result = max { result , plus }
plus = 0
end
write(result)

∵只能选不超过n张邮票
∴算得的结果中上限max只能达到m中面值中最大面值*n（如例题中，最大的结果是4*4=16），下限min显然是面额中最小的数1
但是，从下限1到上限16并不一定都连续，所以我们要找到1到16间不能算得的结果。
∵使用的邮票张数有限制
∴显然用越大的面值可以获得更长的连续结果的可能性更大
∴优先使用大面额的（也就是优先选择获得同一面值时，消耗邮票张数较少的，如：为了获得总面值为4时，优先使用4，而不是2+2 , 2+1+1 , 1+1+1+1这三个）