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

凑零钱 韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里,发现这家店有个特别的规矩:你可以用任何星球的硬币付钱,但是绝不找零,当然也不能欠债。韩梅梅手边有10…

凑零钱

韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里,发现这家店有个特别的规矩:你可以用任何星球的硬币付钱,但是绝不找零,当然也不能欠债。韩梅梅手边有104枚来自各个星球的硬币,需要请你帮她盘算一下,是否可能精确凑出要付的款额。

时间限制:7000

内存限制:65535

输入

输入第一行给出两个正整数:N(≤104)是硬币的总个数,M(≤102)是韩梅梅要付的款额。第二行给出 N 枚硬币的正整数面值。数字间以空格分隔。

输出

在一行中输出硬币的面值V1≤V2≤…≤Vk,满足条件V1+V2+...+Vk=M。数字间以 1 个空格分隔,行首尾不得有多余空格。若解不唯一,则输出最小序列。若无解,则输出 No Solution。

注:我们说序列{ A[1], A[2], … }比{ B[1], B[2], … }“小”,是指存在 k ≥ 1 使得 A[i]=B[i] 对所有 i < k 成立,并且 A[k] < B[k]。

样例输入

样例1:

8 9
5 9 8 7 2 3 4 1

样例2:

4 8
7 2 4 3

样例输出

样例1:

1 3 5

样例2:

No Solution
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1 C++ #include&lt;iostream&gt; #include&lt;algorithm&gt; #include&lt;memory.h&gt; using namespace std; #define inf 0x3f3f3f3f int n,money,a[20000],dp[20000]; struct node { int parent;  int data; }path[20000]; int main() { int i,j; cin&gt;&gt;n&gt;&gt;money; for(i=0;i&lt;n;i++) cin&gt;&gt;a[i]; sort(a,a+n); memset(dp,-inf,sizeof(dp));//初始化为负无穷 for(i=0;i&lt;20000;i++) path[i].parent=-1; dp[0]=0; for(i=0;i&lt;n;i++) { for(j=money;j&gt;=a[i];j--)//次数越多,序列越小,所以我们dp求能构成序列的需要的最多的数  { if(dp[j]&lt;=dp[j-a[i]]+1) { dp[j]=dp[j-a[i]]+1; path[j].parent=j-a[i];//记录路径  path[j].data=a[i];//记录路径元素  }   } } if(dp[money]&gt;0) {    int r[2000],k=0; int temp=money; while(temp!=-1) { r[k++]=path[temp].data; temp=path[temp].parent; } for(i=k-2;i&gt;0;i--)//输出会多一个0,主要是应为dp[0]=0,输出时单独去掉就可以啦  cout&lt;&lt;r[i]&lt;&lt;" "; cout&lt;&lt;r[0]&lt;&lt;endl; } else { cout&lt;&lt;"No Solution"&lt;&lt;endl; } }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 C语言 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #define N 10010 int dp[N], w[N]; int vis[N][N]; void solve() {     int n, m;     scanf("%d %d", &amp;n, &amp;m);     for (int i = 1; i &lt;= n; ++i) scanf("%d", &amp;w[i]);     for (int i = 1; i &lt;= n; ++i)         for (int j = m; j &gt;= w[i]; --j)             if (dp[j] &lt;= dp[j - w[i]] + w[i]) {                 vis[i][j] = 1;                 dp[j] = dp[j - w[i]] + w[i];             }     if (dp[m] != m) printf("No Solution\n");     else {         int a[N];         int v = m, idx = n, count = 0;         while (v &gt; 0) {             if (vis[idx][v]) {                 a[count++] = w[idx];                 v -= w[idx];             }             idx--;         }         for (int i = 0; i &lt; count; ++i) {             printf("%d%s", a[i], (i == count - 1) ? "" : " ");         }     } } int main() {     solve();     return 0; }</pre>
这道题暂未补解析。