计算机考研复试真题 最小邮票数
题目描述
有若干张邮票,要求从中选取最少的邮票张数凑成一个给定的总值。 如,有1分,3分,3分,3分,4分五张邮票,要求凑成10分,则使用3张邮票:3分、3分、4分即可。
输入描述:
有多组数据,对于每组数据,首先是要求凑成的邮票总值M,M<100。然后是一个数N,N〈20,表示有N张邮票。接下来是N个正整数,分别表示这N张邮票的面值,且以升序排列。
输出描述:
对于每组数据,能够凑成总值M的最少邮票张数。若无解,输出0。
示例1
输入
10 5 1 3 3 3 4
输出
3
/*程序设计思路:0-1最小背包问题 方法大概类似于筛选法,题目中已经给出有序,不需要再次排序,对于每一个邮票来说,有且仅有一次使用机会。 所以遍历所有邮票,获取邮票的面值,对于每一个dp数组来说,dp[i]中的i代表总值,dp[i]中保存的数据为个数, 遍历所有小于等于m的i,如果总值减去当前所选的邮票的面值,即i-c[i]合法并且可达,那么i一定可达, 并且dp[i]中的值应该是dp[i-c[i]]的值+1和原来的值中较小的一个。 第二层循环为什么要倒序?因为设想假如正序的话,现在有一张邮票的价值为1,DP[1]会使用到1, DP[2]=min(DP[2],DP[1]+1),这样就相当于使用了两次价值为1的邮票,与题意显然不符合,因此第二层循环一定要倒序。 */ #include<iostream> #include<vector> #define mmax 0x7fffffff using namespace std; int min(int a,int b){return a<b?a:b;} int main() { int m,n; while(cin>>m) { cin>>n; vector<int> c(n); for(int i=0;i<n;i++) //读入N张邮票的面值 cin>>c[i]; vector<int> dp(m+1); for(int i=0;i<=m;i++) dp[i]=mmax; dp[0]=0; for(int i=0;i<n;i++) { for(int j=m;j>=0;j--) //为什么要倒序? { if(j-c[i]>=0&&dp[j-c[i]]!=mmax) { dp[j]=min(dp[j],dp[j-c[i]]+1); } } } if(dp[m]==mmax) cout<<0<<endl; else cout<<dp[m]<<endl; } }