Programming question (algorithm)

VPeric, I'm having trouble with your code even though it makes sense in my head. The coding of it seems to give me a loop that goes on infinitely.

Apparently C always passes arrays as a reference o_O

All the workarounds seem quite involved like creating a structure that hold the array, which can the be passed as a copy by value.

That's probably why my code gets going forever.

Anyone know of an easier way to make this work…
This project is giving me a headache :(

I understand the solutions in my head, but I can't seem to make them work :(

EDIT:

I made a struct. And I passed it on to the function. For some reason my :
solutions+=function(coinsstruct,(Value-coinsstruct.a));
stops subtracting from value after going through one loop …
It just keeps the Value at a constant value and goes through the loop forever…
Should I post my code ?

EDIT2:

Apparently I'm thinking too hard. I'm not supposed to add new things to the main code and basically just use the function call
function(int Value, int coins[], int n)
And I'm supposed to use dynamic programming, basically what you guys said of solving the subproblems first.

EDIT3: The infinite loop is because I put the coins = 0 ….
So then value - 0 = always value
and it keeps going on forever
//SNIP SNIP
I tried making a copy of the coins and copying the elements in.
 
Last edited:
Joined
Nov 13, 2006
Messages
9,193
Location
Manchester, United Kingdom
EDIT: Well, I think you probably didn't read the assignment closely enough? does it state you should use Top-down dynamic programming ? This is something really important before you begin... read the assignment :D In order to use top-down dynamic programming, you need to store each of the earlier solutions you made and use them again in a big array. The way you think needs to be different.

For example you should instead think of 5 2 2 1 as a solution to 10 and 7 2 1 as another soluiton to get 10 save it in an array, now each time you arrive at 10 in your code you use the stored solution. ( This is a very fast way to solve a problem but takes a lot of memory! )


Things are starting to look much better pladio….. the reason I passed sol was to save the solution there. If you make sol a [][] you can store each solution in it. the .length thing could be replaced by length( coins ); ( a function to return the length of the array coins )

However if you print the solution instead directly in the recursive function that makes it a lot easier.

My code was actually java…. but I tried to C-ify it as much as possible… didn't have access to a c compiler at that machine so :p

Also VPeric code is looking good. You also nailed the deep copy thing… although I would probably make a copy function instead! makes your code look a lot cleaner… + you might need to copy some other time too…
 
Last edited:
Joined
Oct 25, 2006
Messages
6,292
GothicGothicness said:
EDIT: Well, I think you probably didn't read the assignment closely enough? does it state you should use Top-down dynamic programming ? This is something really important before you begin… read the assignment :D In order to use top-down dynamic programming, you need to store each of the earlier solutions you made and use them again in a big array. The way you think needs to be different.

For example you should instead think of 5 2 2 1 as a solution to 10 and 7 2 1 as another soluiton to get 10 save it in an array, now each time you arrive at 10 in your code you use the stored solution. ( This is a very fast way to solve a problem but takes a lot of memory! )


Things are starting to look much better pladio….. the reason I passed sol was to save the solution there. If you make sol a [][] you can store each solution in it. the .length thing could be replaced by length( coins ); ( a function to return the length of the array coins )

However if you print the solution instead directly in the recursive function that makes it a lot easier.

My code was actually java…. but I tried to C-ify it as much as possible… didn't have access to a c compiler at that machine so :p

Also VPeric code is looking good. You also nailed the deep copy thing… although I would probably make a copy function instead! makes your code look a lot cleaner… + you might need to copy some other time too…
Click to expand...

We need to do bottom-up and top-down. That's the idea, to see the difference between both.

The assignment spec was very vague to begin with and the lecturer has been amending it as students kept posting comments on how vague it was. It is now finally complete, but the due date hasn't moved :O.

Thanks for the thumbs up for my code :) Makes me feel better, but for some reason it's going in an infinite loop, I think it's because I'm setting the coin to 0 and then V-0 is always V so it never ends. Any ideas ?

Is what I'm doing now the bottom up approach still since I'm not using the solutions again ?
 
Joined
Nov 13, 2006
Messages
9,193
Location
Manchester, United Kingdom
Ok, as far as my C-knowledge goes (which isn't very far, I haven't used it in almost 3 years), your code is missing the bit where you actually remove the largest coin from the list of available coins. So, after you call the recursive function, you ought to remove the largest coin from the list/array, so that the next time you come to the recursive function call, you are trying with different coins (the "second" branch on my graph). Hope that makes some sense...

As far as top-down and bottom-up goes, I'm not exactly clear on the theory of this, so perhaps I'm wrong, but as I understand: what we are doing now is top-down (for one, my graph is orientated that way <grin>). Basically, we say "we have problem X". To solve this, we can do "a, b or c", so lets try to solve our subproblems Xa, Xb and Xc. And then we repeat this until we either find a solution, or realize there can't be one. On the other hand, the bottom up approaches is the one GothicGothicness mentioned, with remembering the solutions: we know how to reach some values (the actual coins), and then we say "Ok, we know how to reach Y, that means we can also reach Ya, Yb and Yc". Lets keep doing everything we can until we get to the solution we'll actually need. I hope that was the correct explanation. <grin>

In any case, I feel the approach you are currently going for/that we suggested is the more perspective, as it's certainly more memory efficient and perhaps even processor-efficient than calculating _all_ the possibilities for _all_ the numbers between 1 and n. [formal proof pending] Of course, neither GothicGothicness nor me know what your teacher exactly wants - maybe he had something completely different in mind. :)
 
Joined
Oct 23, 2006
Messages
585
Location
Serbia
Sorry I didn't reply sooner Pladio… I've been out at a birthday.

Yes that's the buttom up one, you're doing.

I didn't have time yet to go through your code… and my C-compiler is not ready.

But what you should do if you have time is just follow your own code for sometime… start with the array which comes in and see what happens in each step.. that'll usually pinpoint it… even easier if you use a debugger. I'll take a look at it tomorrow to see what is wrong… if you haven't already figured it out!

list of available coins. So, after you call the recursive function, you ought to remove the largest coin from the list/array, so that the next time you come to the recursive function call, you are trying with different coins (the "second" branch on my graph). Hope that makes some sense…
Click to expand...

As far as I understand he is trying to do this by n being less next time the recursive function runs… however perhaps he failed with that… will need to take a closer look.
 
Joined
Oct 25, 2006
Messages
6,292
I checked via debugging and VPeric is right, I keep going through the biggest value again. I don't know how to remove it from the array, because if I put it as 0 all that happens is that Value-0 = Value forever.

And yes I thought that by going through smaller values of n each time it would work, but it doesn't. I would have another look, but I'm not sure how to do it.

I have another class soon, so it will be for later tonight.

Thanks for your help :)
 
Joined
Nov 13, 2006
Messages
9,193
Location
Manchester, United Kingdom
I asked the lecturer about something else again. We are supposed to do this via dynamic programming, as in store everything in a table and basically find the answer via the previous answers that we've found already.

I would try it again. I would let you know what I come up with ...
 
Joined
Nov 13, 2006
Messages
9,193
Location
Manchester, United Kingdom
So that is the approach I described above. Actually that is easier, for you :) So that should be good news...
 
Joined
Oct 25, 2006
Messages
6,292
Sounds like you're trying Memoization (yes, without the R in memorization). Look it up, there are plenty of examples. I could find some for you if you want.
 
Joined
Oct 18, 2006
Messages
7,586
Location
Bergen
Any idea on how to make it so I stop using the biggest coin in VPeric's way ?
I would try your way this evening GG maybe. I also have another way that works now, something I worked on yesterday. I would post it later maybe... I need to iron out some things and I have classes again soon.
 
Joined
Nov 13, 2006
Messages
9,193
Location
Manchester, United Kingdom
for (i=n-1;i>0;i—)
{
printf("%d ",coinscopy);
count = count + possible((V-(coinscopy)),coinscopy,n);
}
Click to expand...


Well, this was obvious once I looked at it… you need to decrease n…. acctually probably you meant to pass in i? not n into the function… but you need to look that over a bit… The way it is now your arrays will never decrease in size! The entire idea with recursion is that you decrease the size of the array after you remove a value from it.
 
Joined
Oct 25, 2006
Messages
6,292
GothicGothicness said:
Well, this was obvious once I looked at it… you need to decrease n…. acctually probably you meant to pass in i? not n into the function… but you need to look that over a bit… The way it is now your arrays will never decrease in size! The entire idea with recursion is that you decrease the size of the array after you remove a value from it.
Click to expand...

Actually, it will decrease the size: note how in the beginning of the function, when he makes coinscopy, it only goes up to n (which will be one lower the next time), so there's just a delay of a one function call. So yes, it's a little wasteful, but it's a good-enough tradeoff for ease of programming, in my opinion.

So yes, put i there and it should work.
 
Joined
Oct 23, 2006
Messages
585
Location
Serbia
I don't think so VPeric?

He doesn't assign a new value to n anywhere.

Anyway as we concluded he should pass i and not n to the function.
 
Joined
Oct 25, 2006
Messages
6,292
Ok. sorry for the late reply. VPeric was right. What the code is doing is going top-down.
Also, I tried changing it to i, but then it is worse than it was before.

//SNIP SNIP

But that doesn't seem to work either. I'm basically making a new array that is smaller than the last one, but it doesn't seem to work…

EDIT: I found out why it's not working now. It's because it's making the array smaller, but then it's going through the loop again which asks for a member of the array which does not exist anymore …

EDIT2;

WOHOOOOO ! I got it to work. I did what VPeric originally suggested. Adapted it to what GG then said :)
I put copy = 0 after it does the recursion, which put it at 0 and gave me my earlier headache. But then I added in if statement that if copy == 0 then it shouldn't go through the recursion again and continue through the loop with the next one. :)

@GG: unlike goto; I can use continue; , right ?

Now I need to find a way to put this in a DPtable :)
 
Last edited:
Joined
Nov 13, 2006
Messages
9,193
Location
Manchester, United Kingdom
Yes continue is fine. Also I would do another solution for the Dynamic programming……. DP table you need to think differently.

1 has one solution which is 1. 2 has two solutions 1 + 1 and 2…. and you go on with 3.

Now when you are up to 25…. to find the different solution you don't acctually need to calculate anything as soon as you reach 24, 10, 5 or whatever you just fetch the solution for that from your table. So as you can see you should make a new solution…. based on this principle.
 
Joined
Oct 25, 2006
Messages
6,292
Yeah, that's the bottom up approach, which I managed to do with some help from someone else :blush:

We're supposed to do both ways and use DP tables for both…
So, VPeric's way is the topdown approach because we do not need to go through all the values, just values that are V - coin -coin and so on…

For some reason I cannot get the possible way to stop going since it's in a recursive stack and so I can't stop the function o_O

By the way, officially I'm not allowed to ask for help, so I would be deleting my posts by tomorrow…

Thanks for everyone's help, especially GG and VPeric for sticking with me till the end :D

EDIT: Got it !!!!! :D :) :) :D
 
Joined
Nov 13, 2006
Messages
9,193
Location
Manchester, United Kingdom
You're welcome. I'm glad that between the three of us, we manage to make a half-decent programmer somehow. ;)

In any case, if you'd like to practice this some more, try this problem. It can be approached with a similar idea.
 
Joined
Oct 23, 2006
Messages
585
Location
Serbia
You're welcome and at least we didn't give you the complete solution... most of it was subtle hints... even if what VPeric posted was pretty near a complete solution :D

Also I wanted to post this quote about dynamic programming..... since you might have been a bit confused about it.

"Top-down dynamic programming simply means storing the results of certain calculations, which are later used again since the completed calculation is a sub-problem of a larger calculation. Bottom-up dynamic programming involves formulating a complex calculation as a recursive series of simpler calculations."
 
Joined
Oct 25, 2006
Messages
6,292
You must log in or register to reply here.
Back
Top Bottom