c++代码--取硬币数最小

#include <iostream> #include <string> #include<limits> using namespace std;

    typedef  struct {     int ncoin;  //使用的硬币数量      int addcoin;  //从上一个状态到当前状态所用      int lasttotal;         }state;      int main() {     /*     给定一个总数，其中硬币种类为1,3,5，且数量不限，求给出最佳的兑换方案：硬币数最少      */     int total=12;     //cin>>total;

    int coin[3]= {1,3,5};     state * sum = (state * )malloc ( sizeof(state) * (total+1));          for (int i =0;i<=total;i++)     {         sum[i].ncoin = 1111;//尽量大的数      }     sum[0].ncoin =0;     sum[0].lasttotal = 0;     for (int i = 1;i<=total;i++)     {         for (int j = 0;j<3;j++)         {             if ( i-coin[j]>=0 && sum[i-coin[j]].ncoin+1<sum[i].ncoin)             {                 sum[i].ncoin = sum[i-coin[j]].ncoin+1;                 sum[i].addcoin = coin[j];                 sum[i].lasttotal = j;             }         }     }     if (sum[total].ncoin == 1111)     {         cout<<" NO CHANGE!!"<<endl;         return 0;     }           else     {         cout<<"least coin number is "<<sum[total].ncoin<<endl;     }         return 0;

}