首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#7328

邮票收集 小A是个邮票收集爱好家,他有n种面值的邮票,每种邮票都有无数张。一天小B想要寄信,需要一共面值和为k的邮票组合。小A想要知道拼出面值为k的邮票最少需要…

邮票收集

小A是个邮票收集爱好家,他有n种面值的邮票,每种邮票都有无数张。一天小B想要寄信,需要一共面值和为k的邮票组合。小A想要知道拼出面值为k的邮票最少需要多少张。

时间限制:1000

内存限制:131072

输入

输入是多组数据。(不超过10组) 每组数据的第一行正整数n,k,表示邮票的种类数目和目标要拼出的钱。(0 < n ≤ 100, 0 < k ≤ 1000 ) 接下来的一行有n个正整数ai(0 < ai ≤ 1000)。 若n=k=0表示输入结束。

输出

每组数据输出一行一个数,分别表示拼出k需要的最少的邮票数量。 如果不存在能够拼出k的方案,输出-1。

样例输入

4 10
1 2 3 4 
5 16
1 2 3 4 5 
2 7
4 5
0 0

样例输出

3
4
-1

提示

第一组数据: 10 = 4+4+2 第二组数据:16 = 5+5+5+1 第三组数据: 不存在。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; const int N = 10005; const int INF = 0x3f3f3f3f; int dp[N]; int w[N]; int t = 11, n, m; int main() {   while (t--) {     cin &gt;&gt; n &gt;&gt; m;     if (n == 0)       break;     for (int i = 1; i &lt;= n; i++)       cin &gt;&gt; w[i];     memset(dp, INF, sizeof(dp));     dp[0] = 0;     for (int i = 1; i &lt;= n; i++)       for (int j = w[i]; j &lt;= m; j++)         dp[j] = min(dp[j], dp[j - w[i]] + 1);     if (dp[m] != INF)       printf("%d\n", dp[m]);     else       printf("-1\n");   }   return 0; }</pre><p><br/></p>
这道题暂未补解析。