邮票问题
本题取材于ICPC(世界赛)95E题
【问题描述】
给定一个信封,最多只允许粘贴N(N<=100)张邮票,我们现在有m(m<=100)种邮票,面值分别为:x1,x2,…….xm分(xi<=255,为正整数),并假设各种邮票都有足够多张.
要求计算所能获得的邮资最大范围,即求最大值MAX,使在1—MAX之间的每一个邮资值都能得到.
例如:N=4,有2种邮票,面值分别为1分,4分,于是可以得到1----10分,和12分,13分,16分的邮资,由于不能得到11分和15分,所有邮资的最大范围是MAX=10.
【样例输入】
从键盘输入一个文本文件的文件名,该文件第1行为最多粘贴的邮票数N;第2行为邮票种数m,以下m行各有一个数字,表示邮票的面值xi.如:
输入:
4
2
1
4
【样例输出】
1. 若最大范围为空,则在屏幕上输出MAX=0
2. 若最大范围不为空,则把结果输出到屏幕上.
输出:
MAX=10.
【算法分析】
本题可以看成是一个集合问题,即求在贴的邮票不多于n张的可满足条件的邮资集.集合问题的关键在于判定元素是否在集合中,对于本题而言,是判断某个邮资是否在贴不多于n张邮票可满足.这个判断问题可以用递归的方法解决.设当前考虑的邮资值为max,最多允许贴n张邮票,记为(max,n).如果首先贴一张面值为xi的邮票,那么剩下的问题是(max-xi,n-1)的问题.如果(max-xi,n-1)可解,那么(max,n)问题也可解.
进一步, 这个递归的算法可以转化为递推的算法来解决.设piece[value]表示邮资为value时所需最少的邮票数, pieces[MAX]=min{pieces[MAX-x[i]]+1}.当pices[value]<=n时,问题(max,n)可解,否则无解.
递推算法可以描述为:
for(i=1;i<=m;i++) if( MAX-x[i]>=0)
{
if(pieces[MAX]==0)
pieces[MAX]=pieces[MAX-x[i]]+1;
if(pieces[MAX]>pieces[MAX-x[i]]+1)
pieces[MAX]=pieces[MAX-x[i]]+1;
}
|
value |
Pieces[value] |
|
0 |
0 |
|
1 |
min{piece[1-1]+1}=1 |
|
2 |
min{piece[2-1]+1}=2 |
|
3 |
min{piece[3-1]+1}=3 |
|
4 |
min{piece[4-1]+1,pieces[4-4]+1}=1 |
|
5 |
min{piece[5-1]+1,pieces[5-4]+1}=2 |
|
6 |
min{piece[6-1]+1,pieces[6-4]+1}=3 |
|
7 |
min{piece[7-1]+1,pieces[7-4]+1}=4 |
|
8 |
min{piece[8-1]+1,pieces[8-4]+1}=2 |
|
9 |
min{piece[9-1]+1,pieces[9-4]+1}=3 |
|
10 |
min{piece[10-1]+1,pieces[10-4]+1}=4 |
|
11 |
min{piece[11-1]+1,pieces[11-4]+1}=5 (>4) |
例程:
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
int x[256];//各种邮票的面值
int pieces[30001];// 邮资为value时所需最少的邮票数,
int i,j,m,n,MAX;
while(cin>>n>>m)
{
for(i=1;i<=m;i++)
cin>>x[i];
memset(pieces,0,sizeof(pieces));
MAX=0;
while(1)
{
MAX++;//计算邮资为MAX最少需要的邮票张数
for(i=1;i<=m;i++)
if( MAX-x[i]>=0)
{
if(pieces[MAX]==0)
pieces[MAX]=pieces[MAX-x[i]]+1;
if(pieces[MAX]>pieces[MAX-x[i]]+1)
pieces[MAX]=pieces[MAX-x[i]]+1;
}
//判断所需最少邮票张数是否超过n张
if(pieces[MAX]==0||pieces[MAX]>n)
{
cout<<"MAX="<<MAX-1<<endl;
break;
}
}
}
return 0;
}