最少钱币数

蔚落 2022-04-24 11:36 166阅读 0赞

【问题描述】这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了 6 种钱币面值为 2、5、10、20、50、100，用来凑 15 元，可以用 5 个 2 元、1个 5 元，或者 3 个 5 元，或者 1 个 5 元、1个 10 元，等等。显然，最少需要 2 个钱币才能凑成 15 元。  
        你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。

【输入形式】输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值 M（1 <= M<= 2000，整数），接着的一行中，第一个整数 K（1 <= K <= 10）表示币种个数，随后是 K个互不相同的钱币面值 Ki(1 <= Ki <= 1000)。输入 M=0 时结束。

【输出形式】每个测试用例输出一行，即凑成钱数值 M 最少需要的钱币个数。如果凑钱失败，输出“Impossible”。你可以假设，每种待凑钱币的数量是无限多的。

【样例输入】

15  
6 2 5 10 20 50 100  
1  
1 2  
0

【样例输出】

2  
Impossible

dp算法

\#include<iostream>  
using namespace std;  
int main() \{  
    int a,i,i1,n,j,k,min,t=0,temp,s=0,t1,sign=0;  
    while(cin>>a) \{  
        if(a==0) break;  
        cin>>n;  
        int z\[n\],s\[a+1\]\[n\];  
        for(i=0; i<n; i++) cin>>z\[i\];  
        //升序   
        for(i=0; i<n-1; i++) \{  
            for(j=0; j<n-1-i; j++) \{  
                if(z\[j\]>z\[j+1\]) \{  
                    temp=z\[j\];  
                    z\[j\]=z\[j+1\];  
                    z\[j+1\]=temp;  
                \}  
            \}  
        \}  
        for(i=0;i<n;i++)\{  
            s\[0\]\[i\]=0;  
        \}  
        for(i=1;i<a+1;i++)\{  
            for(j=0;j<n;j++)\{  
                i1=i;  
                if(z\[j\]>i1) s\[i\]\[j\]=-1;  
                else if(z\[j\]==i1) s\[i\]\[j\]=1;  
                else if(z\[j\]<i1)\{  
                    i1=i1-z\[j\];  
                    min=-1;  
                    sign=0;  
                    for(k=0;k<n;k++)\{  
                        if(s\[i1\]\[k\]!=-1&&sign==0)\{  
                            min=s\[i1\]\[k\];  
                            sign=1;  
                        \}  
                        else if(s\[i1\]\[k\]!=-1&&min>s\[i1\]\[k\])\{  
                            min=s\[i1\]\[k\];  
                        \}  
                    \}  
                    if(min==-1) s\[i\]\[j\]=-1;  
                    else s\[i\]\[j\]=min+1;  
                \}  
            \}  
        \}  
        sign=0;  
        min=-1;  
        for(i=0;i<n;i++)\{  
            if(s\[a\]\[i\]!=-1&&sign==0)\{  
                min=s\[a\]\[i\];  
                sign=1;  
            \}  
            if(s\[a\]\[i\]!=-1&&min>s\[a\]\[i\])\{  
                min=s\[a\]\[i\];  
            \}  
        \}  
        if(min==-1)cout<<"Impossible"<<endl;  
         else cout<<min<<endl;  
//         cout<<"——————————————————"<<endl;  
//         for(i=0;i<a+1;i++)\{  
//             for(j=0;j<n;j++) cout<<s\[i\]\[j\]<<' ';  
//             cout<<endl;  
//         \}  
//         cout<<"——————————————————";  
    \}  
    return 0;  
\}