#include <iostream>
#define MAX 20
int c[MAX];//存储所有币值
int F[MAX];//存放1到n的各个值所需的币数

int min(int x,int y)  //取较小值函数
{
    return (x<y)?x:y;
}

int changeMaking(int D[],int m,int n) //m为D的len,n为金额
    {   int i;
        F[0]=0;
        printf("start m=%d n=%d\n",m,n);
        for(i=1;i<=n;i++) //从1 到n的各个值所需的币数
            {
            printf("+++++++++++++++++++++++++++++++++++++++start i=%d$ \n",i);
                int temp=10000,j=1;
                while(j<=m and i>=D[j])//选择，并且选择之后在总数的范围类
                {
                    int lasttemp=temp;
                    temp=min(F[i-D[j]],temp);//选择了之后，之前子问题最优值，本质是将问题分段，分为已解决和未解决的部分
                    //例如，总数为5，选择1，那么就要使用F[5-1]的值，如果使用5，那么就是使用F[5-5]的值
                    printf("start select D[%d]=%d$, <before F[%d=%d-%d]=%d$ min=%d> %d\n",j,D[j],i-D[j],i,D[j],F[i-D[j]],temp,lasttemp);
                    j=j+1;
                }

                F[i]=temp+1;
                printf("++++++++++++++++++++++++end F[%d]=%d$ \n",i,F[i]);


            }
        return F[n];
    }
//int main_ningqian()
int main()
{
    int n=3,m=15;

    c[1]=1;//可以凑齐
    c[2]=5;
    c[3]=11;

/*
    c[1]=2;//不能凑齐
    c[2]=4;
    c[3]=10;
*/

    /*
    printf("请输入有多少个纸币：");
    scanf("%d", &n);
    printf("请分别输入纸币的价值：");
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &c[i]);

    }
    printf("请输入金额：");
    scanf("%d", &m);
    */


    int number=changeMaking(c,n,m);
    printf("changeMaking=%d\n",number);

     int j=m,i,num=0;
     int arr[MAX];
     while(j>0)
     {
         for(i=n;i>0;i--)
         {
             if(j-c[i]>=0 and F[j-c[i]]==number-1) //要求j-c[i]>=0才有效，否则可能为负，而且F[]的值符合要求
             {
                 arr[num++]=c[i];
                 j=j-c[i];
                 number=number-1;
                 break;  //找到符合要求的币值，则break
             }
             else{ continue;}
         }
     }

     printf("find:");
     for (int i = 0; i<num; i++)

         printf("%d ", arr[i]);
     return 0;
}