最少硬币问题.txt

来自「算法设计与分析源代码算法设计与分析源代码」· 文本 代码 · 共 60 行

#include<iostream> 
using namespace std; 
int main() 
{ 
int n,i,m,t,v; 

cin>>n; 
int *value=new int [n+1],*value1=new int [n+1]; 
int *q=new int [n+1]; 
      for(i=1;i<=n;i++) 
  { cin>>value[i]>>q[i]; 
  value1[i]=value[i]*q[i];} 
        cin>>m; 
    int *way=new int [m+1]; 
int *way1=new int [m+1]; 
way1[0]=way[0]=0; 
for(i=1;i<=m;i++) 
{ 
if(value1[1]>=i&&i%value[1]==0) 
way1[i]=way[i]=i/value[1]; 
        else  
way1[i]=way[i]=0; 

} 

int j; 
for(j=2;j<=n;j++) 
{ 
         for(i=value[j];i<=m;i++) 
 {     
              
 t=1; 
 while(t<=q[j]&&value[j]*t<=i) 
 {         
                   if((i-value[j]*t)&&way[i-value[j]*t]==0) 
   {   t++; 
   continue;} 
   else 
   v=t+way[i-value[j]*t]; 
   if(way1[i]==0||way1[i]>v) 
      way1[i]=v; 
   t++; 
 } 
 } 

         for(i=1;i<=m;i++) 
 { way[i]=way1[i]; 
  

 } 
            
} 
if(way[m]==0) 
way[m]=-1; 
cout<<way[m]<<endl; 


return 0; 
}