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[i]));
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[i] = 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.

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 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

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…

Originally Posted by GothicGothicness
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 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

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…

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[i] 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 ?

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.

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…

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.

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

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 …

So that is the approach I described above. Actually that is easier, for you So that should be good news…

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.

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.

for (i=n-1;i>0;i—)
{
printf("%d ",coinscopy[i]);
count = count + possible((V-(coinscopy[i])),coinscopy,n);
}

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.

Originally Posted by GothicGothicness
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.

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.

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.

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[i] = 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[i] == 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

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.

Yeah, that's the bottom up approach, which I managed to do with some help from someone else

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

EDIT: Got it !!!!!

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.

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

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."

Ok, I am very confused about top-down and bottom-up now
Well, I hope I pass the stupid task though.

Snipping off my code now. Hope you don't mind….