Code: Select all
#include <iostream>
using namespace std;
#include <cstring>
#include <cstdio>
#include <cmath>
//#include <fstream>
//ifstream fin("in.txt");
//#define cin fin
int shop[501];
int min;
int money;
int numOfCoin[7];
int num;
void init()
{
int i,j;
int cnt;
memset(shop,0,sizeof(shop));
for(i=500;i>=5;i-=5)
{
j=i;
cnt=0;
if(j>=200)
{
cnt+=j/200;
j%=200;
}
if(j>=100)
{
cnt+=j/100;
j%=100;
}
if(j>=50)
{
cnt+=j/50;
j%=50;
}
if(j>=20)
{
cnt+=j/20;
j%=20;
}
if(j>=10)
{
cnt+=j/10;
j%=10;
}
if(j>=5)
{
cnt+=j/5;
j%=5;
}
shop[i]=cnt;
}
}
void backtrack(int type,int cnt,int sum)
{
if(sum>=money)
{
if(num+shop[sum-money]<min)
min=num+shop[sum-money];
return ;
}
if(type>6)
return;
if(cnt<numOfCoin[type])
{
switch(type)
{
case 1:sum+=5;break;
case 2:sum+=10;break;
case 3:sum+=20;break;
case 4:sum+=50;break;
case 5:sum+=100;break;
case 6:sum+=200;break;
}
num++;
backtrack(type,cnt+1,sum);
switch(type)
{
case 1:sum-=5;break;
case 2:sum-=10;break;
case 3:sum-=20;break;
case 4:sum-=50;break;
case 5:sum-=100;break;
case 6:sum-=200;break;
}
num--;
backtrack(type+1,0,sum);
}
else
{
backtrack(type+1,0,sum);
}
}
int main()
{
int i,j;
double temp;
init();
while(1)
{
j=0;
for(i=1;i<7;i++)
{
cin>>numOfCoin[i];
j+=numOfCoin[i];
}
if(j==0)
break;
cin>>temp;
money=int(temp*1000)/10;
min=99999999;
num=0;
backtrack(1,0,0);
printf("%3d\n",min);
}
return 0;
}
0 5 1 0 1 9 1.55
my program output : 4
but i see someone output :3
which one is right??
thanks!