674 - Coin Change

[Alexei Rybalkin]

Thank you and good luck!

[Alexei Rybalkin]

But I don't know what's wrong with my algorithm...

Can you help me?

Thanks

[cpp]
The code is wrong
[/cpp]

[Aleksandrs Saveljevs]

The reason is that it should be done this way:

Having computed the number of ways to do it with k coins, compute the number of ways of doing it with k+1 coins. That means, you must add only 1 coin at a time. PS: From this point of view, it's hard to interpret what your code does.

Also, you should change "long m[7489]" to "long m[7490]".

Good luck!

[Alexei Rybalkin]

My code is wrong

[Zhao Le]

I know my algorithm is bad also wanna know how to use DP in my algorithm.
Thanks in advance.
[cpp]#include <iostream.h>

void C5(int n,int& count)
{
if(n >= 5)
{
n /= 5;
count += n;
}
}

void C10(int n,int& count)
{
if(n >= 10)
{
while(n >= 10)
{
n -= 10;
count++;
C5(n,count);
}
}
}

void C25(int n,int& count)
{
if(n >= 25)
{
while(n >= 25)
{
n -= 25;
count++;
C10(n,count);
C5(n,count);
}
}
}

void C50(int n,int& count)
{
while(n >= 50)
{
n -= 50;
count++;
C25(n,count);
C10(n,count);
C5(n,count);
}
}

void main()
{
int n;
while(cin>>n)
{
int count = 0;

if(n>=50)
{
C50(n,count);
C25(n,count);
C10(n,count);
C5(n,count);
}
else if(n>=25)
{
C25(n,count);
C10(n,count);
C5(n,count);
}
else if(n>=10)
{
C10(n,count);
C5(n,count);
}
else if(n>=5) C5(n,count);

cout<<count+1<<endl;
}
}[/cpp]

[Zhao Le]

The time is not always the same.
Next sumbit will surely give you a suprise.

[sohel]

Hi,
From your code it looks like you are using brute force. And that should obviously get TLE.

Implementation of DP:
1) declare an int array of size 7500
2) initialize all the elements with 0
3) set Array[0] = 1; --- because there is only one way of making zero ie
'by not choosing any coin'.

4) for every coin run a loop from j = 1 to 7500
set Array[ coinvalue + j] += Array[j];
5) END

Hope it helps.

[Zhao Le]

Thanks for your reply.
the forth step in your DP implementation make me confused.
what is coinvalue? 1,5,10,25,50?
but when j=7500
how can j+coin refers? (like S[7500+50])

[shamim]

what is coinvalue? 1,5,10,25,50?

yes these are the coin value.

but when j=7500
how can j+coin refers? (like S[7500+50])

the idea is S[7500+50], that is S[8000] can be made by numer of ways
S[8000] has already been made, plus the number of ways S[7500] can be made.
Because, of all the ways we made S[7500], to each if we add 50 we will get S[8000].

[Tahseen Mohammad]

I think you're asking shouldn't S[7500 + 50] get RTE.
The answer is yes

your loop for 'j' should be something like this:

Code: Select all

for (j = 0; j + coin <= 7500; ++j)

Hope I get your question right & the answer helps.

[multicast]

I think that the response are correct but judge replay TLE

Please someone help me

[shamim]

Hi, You should use dynamic programming to store the results in a table and then give output from the table, corresponding to an input.

[multicast]

Hi, You should use dynamic programming to store the results in a table and then give output from the table, corresponding to an input.

I know that i Should.

Can you help me to do

[multicast]

shamim,

thank you very much

I found de bug

[58050zz]

plz help

i think i can solve
but Stack Overflow

i use MS VC++
if i use ctrl+F5
run program normally(looks normally,no result)

if in debug,he say
Unheandled exception in win.exe: 0xc00000FD: Stack Overflow

i can only solve the problem under 277

i try to change 'int way' and 'int coin_mount[N]'
to long,but no use

Code: Select all

57<==input
62<==output
129
558
134
628
239
4353
277
7098

Code: Select all

#include <iostream>
#include <string>
using namespace std;
#define N 5
//#define OUTPUT 1

int Dollars(const int value[N],long coin_mount[N],
			const int &target,
			int where,long &way,int counter)
{	
	int i,gether=0,howmany=0
		,left=target;
	int amount=0;

	for(i=where;i<N;i++)
	{ 
		if(value[i]<=left && left>0 )
		{
			where=i;	//find the tail
			coin_mount[i]=left/value[i];		
			left=target%value[i];	
		}
		else
		{
			coin_mount[i]=0;
		}
	}
#ifdef OUTPUT
	for(i=0;i<N;i++)
	{
		if(coin_mount[i])
		{
			amount+=coin_mount[i]*value[i];
		}
		cout<<coin_mount[i]<<",";
	}
	cout<<" NT="<<amount;
	cout<<endl;	
#endif	

	for(int i2=where;i2>=0;i2--)
	{
		
		if(i2==N-1) 
		{
			continue;
		}
		if(coin_mount[i2])
		{
			coin_mount[i2]--;
			int target2=value[i2];
			for(int i5=i2+1;i5<N;i5++)
			{
				target2+=coin_mount[i5]*value[i5];
			}
			return Dollars(value,coin_mount,target2,i2+1,++way,0);
			//i2 is where in this recursion
		}
		else
		{
			if(i2==0 && coin_mount[0]==0)
			{
				return way+1;
			}			
		}
	}	

}

int main()
{
	//5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent.
	int value[N]={50, 25, 10 ,5,1};	
	int target=500;
	//target*=100;
	//set target as input~~
	long coin_mount[N]={0};

	while(cin>>target)
	{
			long way=0;
			  if(cin.eof()) 
				  return 0; 

	int ans=Dollars(value,coin_mount,target,0,way,0);
	cout<<ans<<endl;
	}


	return 0;
}