设有n种不同面值的硬币,各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱,可以实用的各种面值的硬币个数不限。当只用硬币面值T[1],T[2],…,T[i]时,可找出钱数j的最少硬币个数记为C(i,j)。若只用这些硬币面值,找不出钱数j时,记C(i,j)=∞。
输入结果保存在1.txt中,输出结果保存在2.txt中。
#include<iostream> #include <fstream> using namespace std; int change_coin(int a[],int k,int ch) { int **c=new int*[k]; for(int i=0;i<k;i++) c[i]=new int[ch+1]; for(i=0;i<=ch;i++) { if(ch%a[0]==0) c[0][i]=i/a[0]; else c[0][i]=INT_MAX; } for(int j=1;j<k;j++) { for(i=0;i<=ch;i++) if(i<a[j]) c[j][i]=c[j-1][i]; else c[j][i]=c[j-1][i]<c[j][i-a[j]]+1?c[j-1][i]:c[j][i-a[j]]+1; } return c[k-1][ch]; } int main() { int k; int a[3]; int ch; ifstream in("1.txt"); ofstream out("2.txt"); in>>k; for(int i=0;i<k;i++) in>>a[i]; cout<<"请输入待找钱数"<<endl; cin>>ch; int res=change_coin(a,k,ch); cout<<"找钱个数为:"<<res<<endl; out<<res; in.close(); out.close(); return 1; }