f******5
发帖数: 11 | 1 help needed with C++ code of the algorithm
Input: n=total amount of money
Check denomination: a1,a2, …..ak..
Output: minimum amount change=money[n]
1 money[0]=0
2 money[1]=1
3 for I from 2 to k
4 min_tmp=n
5 for j from 0 to n
6 if i>=aj
7 min_tmp=min(money[i-aj] +1, min_tmp)
8 money[i]=min_tmp;
thanks | c***r
发帖数: 1570 | | f******5
发帖数: 11 | 3 It compiles!!
#include
using namespace std;
int moneyChange(int *money, int len, int i);
int main(void)
{
int len=11;
int money[]={0,1,0,0,0,0,0,0,0,0,0};
int amount=10;
moneyChange(money, 11, 10);
for (int i=0;i
cout<
system("pause");
return 0;
}
int moneyChange(int *money, int , int i){
int min_temp=i;
int denom[3]={1, 3, 4};
if (i==0) return 0;
else if (i==1) return 1;
else{
for( int j=0 ; j<3; j++){
if (i>=denom[j])
{
int k=( i-denom[j] );
int changeNum=moneyChange(money, 11, k);
min_temp=min(changeNum+1, min_temp);
}
}
money[i]=min_temp;
return money[i];
}//end of else
}//end of moneyChange
int min(int a, int b){
if(a>b)
return b;
else
return a;
}
【在 c***r 的大作中提到】
: vector.sort
|
|
