|
Your donations keep RPGWatch running!
Programming question (algorithm)
March 15th, 2011, 11:02
Hi,
I have a course on algorithms this semester. I know there are quite a few programmers here, so this should be quite simple for you. I just spent 5 hours trying to figure it out in the lab, but couldn't and I'm pretty sure the answer is quite simple.
Basically, you have an ordered list of numbers:
2
3
5
5
10
20
25
30
And what you need to do is with those 'coins' give change for a 35$ note or whatever.
So what I need to do is go through all the possible iterations and match all the possibilities.
I tried doing a bubble sort kind of thing.
So what I did was:
for loop from first element in array to last (i);
{
for loop from last element of coin array to current value of i;
{
check if value = 35; then add to counter of possible ways of giving change;
check if value < 35;
{
then add to total;
if total = 35 then add to counter;
if total > 35 remove that number from the total again
}
}
}
The problem with this is that it only goes through the number once. What I mean is that let's say it manages to find out that 30+5 = 35. It then goes to the next lower value in the coin array 25 instead of finding the other 30+5 and the 30+3+2.
I hope you understand what I am talking about.
I need a way to go through each possibility. Any suggestions.
Programming in C by the way.
Thanks.
I have a course on algorithms this semester. I know there are quite a few programmers here, so this should be quite simple for you. I just spent 5 hours trying to figure it out in the lab, but couldn't and I'm pretty sure the answer is quite simple.
Basically, you have an ordered list of numbers:
2
3
5
5
10
20
25
30
And what you need to do is with those 'coins' give change for a 35$ note or whatever.
So what I need to do is go through all the possible iterations and match all the possibilities.
I tried doing a bubble sort kind of thing.
So what I did was:
for loop from first element in array to last (i);
{
for loop from last element of coin array to current value of i;
{
check if value = 35; then add to counter of possible ways of giving change;
check if value < 35;
{
then add to total;
if total = 35 then add to counter;
if total > 35 remove that number from the total again
}
}
}
The problem with this is that it only goes through the number once. What I mean is that let's say it manages to find out that 30+5 = 35. It then goes to the next lower value in the coin array 25 instead of finding the other 30+5 and the 30+3+2.
I hope you understand what I am talking about.
I need a way to go through each possibility. Any suggestions.
Programming in C by the way.
Thanks.
March 15th, 2011, 11:23
This is a classic programming problem, if you don't care about performance that would be really simple. This method won't get that poor performance either if you setup your data types correctly.
To build 35, first take the largest number which is smaller than 35, after that find the largest number which adds to that number without exceeding 35. Repeat until 35 is reached. That way you would first get 30 + 5 ( 5 is the largest possible number you can combine with 30 without exceeding 35 ) after that you'd get 30 + 3 ( because 3 is the largest number except for 5 which you can combine ) than you'd get 33 + 2 ( because two is the largest number you could combine with 33 without exceeding 35 ), when you are done with all 30 possiblitles remove 30 ( the largest number ) and do same process for 25 second largest.
Hope this explanation made sense….. I've been known to not make sense when I explain too fast
To build 35, first take the largest number which is smaller than 35, after that find the largest number which adds to that number without exceeding 35. Repeat until 35 is reached. That way you would first get 30 + 5 ( 5 is the largest possible number you can combine with 30 without exceeding 35 ) after that you'd get 30 + 3 ( because 3 is the largest number except for 5 which you can combine ) than you'd get 33 + 2 ( because two is the largest number you could combine with 33 without exceeding 35 ), when you are done with all 30 possiblitles remove 30 ( the largest number ) and do same process for 25 second largest.
Hope this explanation made sense….. I've been known to not make sense when I explain too fast
March 15th, 2011, 11:54
Yeah, thanks.
I understand that with my head, but I can't seem to make my algorithm use every number.
As in, I want it to try coins[0], coins[1], coins[2],…,coins[n]
then I want it to try coins[0]+coins[1],coins[0]+coins[2],…coins[0]+coins[n]
then I want it to try coins[1]+coins[2],coins[1]+coins[3],…coins[1]+coins[n]
But I also want it to do
coins[0]+coins[1]+coins[2], coins[0]+coins[1]+coins[3],…, coins[0]+coins[1]+coins[n]
coins[1]+coins[2]+coins[3], coins[1]+coins[2]+coins[4],…, coins[1]+coins[2]+coins[4].
It just seems like I need an infinite amount of loops
Could u be more specific ?
I understand that with my head, but I can't seem to make my algorithm use every number.
As in, I want it to try coins[0], coins[1], coins[2],…,coins[n]
then I want it to try coins[0]+coins[1],coins[0]+coins[2],…coins[0]+coins[n]
then I want it to try coins[1]+coins[2],coins[1]+coins[3],…coins[1]+coins[n]
But I also want it to do
coins[0]+coins[1]+coins[2], coins[0]+coins[1]+coins[3],…, coins[0]+coins[1]+coins[n]
coins[1]+coins[2]+coins[3], coins[1]+coins[2]+coins[4],…, coins[1]+coins[2]+coins[4].
It just seems like I need an infinite amount of loops

Could u be more specific ?
March 15th, 2011, 12:17
Well, this is typically a case where recursive programming is best. I wouldn't use for loops for this.
Did you learn recursive programming?
think while loop with conditions rather than for loops. Or calling the same function over and over again ( recursion ) this is a bit tricky to do in C though as you could end up filling the machine memory.
Did you learn recursive programming?
think while loop with conditions rather than for loops. Or calling the same function over and over again ( recursion ) this is a bit tricky to do in C though as you could end up filling the machine memory.
March 15th, 2011, 12:28
That's what we're supposed to be learning now. I would try again tomorrow and I would bring the whole code with me to RPGWatch 
Maybe I can get it to work then …
What u mean is…
while (i>0)
{
while(false)
{
call recursive function which goes through the other possibilities and returns true when done ?
}
i--
}

Maybe I can get it to work then …
What u mean is…
while (i>0)
{
while(false)
{
call recursive function which goes through the other possibilities and returns true when done ?
}
i--
}
March 17th, 2011, 14:44
Anything you can do linearly can be done recursively. To make it fully recursive, remove the while loop with a recursive function call.
Sloppy inefficient non-modular pseudo-code:
Sloppy inefficient non-modular pseudo-code:
Code:
int coins = { 50,25,10,1 };
int nCoins = 4;
// returns biggest coin that can be used as money, and returns it
// or a 0 if we can't make change
int getBiggestCoin(int money)
{
int i = 0;
int coin = 0;
// if smallest coin is too big, give up
if(coins[nCoins-1] > money)
return 0;
// look through until we find the right coin
while(coins[i] > money && i < nCoins)
i++;
return coins[i];
}
int makeChange(int amount)
{
int change;
while(change = getBiggestCoin(amount)) // when change returns 0, while loop terminates
{
print("%d ", change); // print out coin value
amount -= change; // deduct from total
}
if(amount > 0)
print("\nCouldn't make change for last %d cents.", amount);
}
Traveler
March 17th, 2011, 18:56
I'm too lazy to contribute a solution, so I'll critique instead. 
ecliptic, your function is still iterative. For your function to be recursive it need to call itself (preferably as the last step in the computation). You should also avoid using global variables like coins and nCoins and instead make them arguments of the function.

ecliptic, your function is still iterative. For your function to be recursive it need to call itself (preferably as the last step in the computation). You should also avoid using global variables like coins and nCoins and instead make them arguments of the function.
Level N+1
March 17th, 2011, 19:56
Also, that solution just picks the answer that uses the fewest number of coins. The OP was looking for a solution that shows all possible answers, methinks.
March 17th, 2011, 23:34
Change-making problem
Code:
Option Explicit
'VB6 Code by HiddenX 2011
Const maxindex As Long = 5
Dim coin(1 To maxindex) As Long
Dim change As Long
Sub Init()
coin(5) = 25
coin(4) = 20
coin(3) = 10
coin(2) = 5
coin(1) = 1
change = 99
End Sub
'Greedy Algorithm - recursive
Sub coincheck(value As Long, index As Long)
If value >= coin(index) Then
Debug.Print coin(index) & ","
value = value - coin(index)
If value = 0 Then
Debug.Print "<Ready>"
Else
coincheck value, index
End If
Else
index = index - 1
If index >= 1 Then
coincheck value, index
Else
Debug.Print "<Cancel>"
End If
End If
End Sub
'Main
Private Sub Form_Load()
Init
coincheck change, maxindex
End Sub
March 18th, 2011, 05:15
Yeah, like Thrasher said, I'm looking for all possibilities. I don't need to list all of them, but need to count them.
HiddenX's code seems to make the most sense to me for now, but I would need to fix it to C and I'm not that familiar with VB. Also I tried a new method and would post it later today… Going to eat now. thanks for all of your help. I would show you what I've got later
HiddenX's code seems to make the most sense to me for now, but I would need to fix it to C and I'm not that familiar with VB. Also I tried a new method and would post it later today… Going to eat now. thanks for all of your help. I would show you what I've got later
March 18th, 2011, 07:27
By the way, I'm required to do this bottom up, top down and with data structures.
But if I can just find a way to make it work simply first that would be good
//SNIP SNIP
Mini explanation:
counter counts up whenever it finds a total of the right value.
Value is the necessary value
number is the amount of available coins
coins[] is the array with the possible coins
total sums up the value to be compared to V
sum() the function is used to add a multiple of a certain coin to the total.
Now. Easy example:
I get V = 13
and coins[]: 2,3,5
So the correct possibilities are:
2,2,2,2,2,3
2,2,3,3,3
2,3,3,5
2,2,2,2,5
3,5,5
Hope all of this makes sense.
Now my code can find everything except for 2,3,3,5
This is because it doesn't know how to go through permutations of 3 or more coin types.
Any way to achieve this ?
Or is my way of doing this a complete mess and I should start all over ? o.O
But if I can just find a way to make it work simply first that would be good

//SNIP SNIP
Mini explanation:
counter counts up whenever it finds a total of the right value.
Value is the necessary value
number is the amount of available coins
coins[] is the array with the possible coins
total sums up the value to be compared to V
sum() the function is used to add a multiple of a certain coin to the total.
Now. Easy example:
I get V = 13
and coins[]: 2,3,5
So the correct possibilities are:
2,2,2,2,2,3
2,2,3,3,3
2,3,3,5
2,2,2,2,5
3,5,5
Hope all of this makes sense.
Now my code can find everything except for 2,3,3,5
This is because it doesn't know how to go through permutations of 3 or more coin types.
Any way to achieve this ?
Or is my way of doing this a complete mess and I should start all over ? o.O
Last edited by Pladio; March 25th, 2011 at 02:13.
March 18th, 2011, 10:22
Again, do it recursively instead. I would start over ( especially you should know if you use goto you're going the wrong way
Here is a little hint how to do it recursively, to find one solution. If we posted the complete solution like HiddenX you'd learn nothing…
Now if you modify this soltution some it could be used to find all permutations.
It is importnat to understand the concept of deep copy and shallow copy also, when you program recursively in C, it is a very common mistake to get a shallow copy ( just the pointer ) instead of copying the actual data in the recursive function.
add, and remove adds / or removes coins from the array. Also this function can be made shorter fairly easily…. but I made it a bit easier to read.
Here is a little hint how to do it recursively, to find one solution. If we posted the complete solution like HiddenX you'd learn nothing…Code:
static int[] getComb(int amount, int[] coins, int[] sol){
if( amount == 0)
return sol;
else if( amount < 0 || coins.length <= 0)
return null;
if( coins[0] > amount )
coins = remove(coins,0);
else{
amount -= coins[0];
sol = add(sol, coins[0]);
coins = remove(coins,0);
}
return getComb(amount, coins, sol);
}
It is importnat to understand the concept of deep copy and shallow copy also, when you program recursively in C, it is a very common mistake to get a shallow copy ( just the pointer ) instead of copying the actual data in the recursive function.
add, and remove adds / or removes coins from the array. Also this function can be made shorter fairly easily…. but I made it a bit easier to read.
March 19th, 2011, 05:19
Is it unique 'combinations' or unique 'sequences'?
Like, is "1,5,10" considered the same as "10,5,1"?
I feel like that would make the solution trickier.
Like, is "1,5,10" considered the same as "10,5,1"?
I feel like that would make the solution trickier.
Traveler
March 19th, 2011, 06:17
Thanks, GG I would try out later or tomorrow. Need to catch up on other stuff to.
Ecliptic, yeah they're the same…
Ecliptic, yeah they're the same…
March 19th, 2011, 10:24
I guess as long as you're systemic about how you change coin sizes it won't be an issue.
Traveler
March 19th, 2011, 14:42
Originally Posted by GothicGothicnessGG, what's coinslength in your code ? And add(sol,coins[0]) ? and remove (coins,0) ?
Again, do it recursively instead. I would start over ( especially you should know if you use goto you're going the wrong wayHere is a little hint how to do it recursively, to find one solution. If we posted the complete solution like HiddenX you'd learn nothing…
Now if you modify this soltution some it could be used to find all permutations.Code:static int[] getComb(int amount, int[] coins, int[] sol){ if( amount == 0) return sol; else if( amount < 0 || coins.length <= 0) return null; if( coins[0] > amount ) coins = remove(coins,0); else{ amount -= coins[0]; sol = add(sol, coins[0]); coins = remove(coins,0); } return getComb(amount, coins, sol); }
It is importnat to understand the concept of deep copy and shallow copy also, when you program recursively in C, it is a very common mistake to get a shallow copy ( just the pointer ) instead of copying the actual data in the recursive function.
add, and remove adds / or removes coins from the array. Also this function can be made shorter fairly easily…. but I made it a bit easier to read.
March 19th, 2011, 14:49
HiddenX, a closer look at your code… It only find one value and then returns it. It doesn't go through anymore values once it has found one.
March 19th, 2011, 15:50
Woohoo, I got something to work for two numbers… Made my own code too. Can anyone tell me or give me a good pointer as to make it work for more than two numbers ?
// SNIP SNIP
// SNIP SNIP
Last edited by Pladio; March 25th, 2011 at 02:13.
March 19th, 2011, 17:11
Pladio, first of all, your code will not generalize to more than 2 coins, so don't even try.
However, the code from GothicGothicness is good:
Anyway, here's my attempt at an explanation:
Lets say that we need to split 35, using coins of 5, 10 and 20 (for simplicity). So, we could represent our data with the following graph (no, it's not pretty, and yes, a part is missing on the right side, but I was tired!):

So, what are we doing here? We start with some amount, and then try to use each coin we have (starting from the largest) and see what remains: if the number is 0, we have a solution; if it's negative, we "subtracted" too much and cannot find a solution, and if it's positive we continue with the process. Of course, if we always try every possible coin, we will get duplicates (20, 10, 5 and 5, 10, 20, for example). To solve this problem, we check which number we used the previous time and try with the same coin and smaller ones, but not the larger ones (so, in the rightmost case, when we used -5 right away, we can just keep using -5's and eventually reach a solution). I've tried to label the graph, but at some point I figured it started to be obvious and I didn't bother. <grin> If you have questions, speak up.
So, that's the base idea, now how to translate it to code? It's obviously going to be recursive, as we are just repeating the same steps for every node in the tree. Below, (spoilered), I've tried to write some kind of pseudocode as a solution (I think it will be understandable, and quite close to Java/C++):
Hope that helps!
However, the code from GothicGothicness is good:Code:
static int[] getComb(int amount, int[] coins, int[] sol){
if( amount == 0)
return sol;
else if( amount < 0 || coins.length <= 0)
return null;
if( coins[0] > amount )
coins = remove(coins,0);
else{
amount -= coins[0];
sol = add(sol, coins[0]);
coins = remove(coins,0);
}
return getComb(amount, coins, sol);
}
Originally Posted by PladioGothicGothicness is writing in some sort of pseudocode as far as I can see, but basically the point is this: coins is an array of the available coins, "remove(coins, 0)" is the command that will remove the coin with the index 0 (that is, the biggest coin); similarily, "add(sol, coins[0])" adds the value of coins[0] (that is, the coin used) to the array sol, which is the array of the coins we used to get to our current situation. However, since you don't really need the actual solution, just the number of solutions, the code can be further simplified.
GG, what's coinslength in your code ? And add(sol,coins[0]) ? and remove (coins,0) ?
Anyway, here's my attempt at an explanation:
Lets say that we need to split 35, using coins of 5, 10 and 20 (for simplicity). So, we could represent our data with the following graph (no, it's not pretty, and yes, a part is missing on the right side, but I was tired!):

So, what are we doing here? We start with some amount, and then try to use each coin we have (starting from the largest) and see what remains: if the number is 0, we have a solution; if it's negative, we "subtracted" too much and cannot find a solution, and if it's positive we continue with the process. Of course, if we always try every possible coin, we will get duplicates (20, 10, 5 and 5, 10, 20, for example). To solve this problem, we check which number we used the previous time and try with the same coin and smaller ones, but not the larger ones (so, in the rightmost case, when we used -5 right away, we can just keep using -5's and eventually reach a solution). I've tried to label the graph, but at some point I figured it started to be obvious and I didn't bother. <grin> If you have questions, speak up.
So, that's the base idea, now how to translate it to code? It's obviously going to be recursive, as we are just repeating the same steps for every node in the tree. Below, (spoilered), I've tried to write some kind of pseudocode as a solution (I think it will be understandable, and quite close to Java/C++):
Spoiler
Hope that helps!
Sentinel
March 19th, 2011, 17:44
Wow, thanks for your time. Hope you're not too busy 
It's 2.30 AM now and I was trying to change my code to generalize with more than 2 coin denominations.
If I may explain what I was trying to accomplish.
Basically:
V = c1*x1+c2*x2+…+cn*xn
With two coins: V = c1*x1+c2*x2
<=> x1 = (V-c2*x2)/2
And just keep incrementing x2 would find me all my x1's.
Which works perfectly for two numbers. I thought I was almost done
First of, I would need to keep all the values actually, because part of the idea is to compare bottom up (iterative) method with top down (recursive) method by comparing the amount of cells used in the array.
Well, I get your tree.
I think I get your pseudocode too. But I'm a bit tired and would try again tomorrow, my brain is slowly shutting down.
Tomorrow or Monday I would also need to build up an array that stores all the solutions and knows how many coins were used arg !
Would you believe that last week's task was to just do the Fibonacci sequence in a few ways ?

It's 2.30 AM now and I was trying to change my code to generalize with more than 2 coin denominations.
If I may explain what I was trying to accomplish.
Basically:
V = c1*x1+c2*x2+…+cn*xn
With two coins: V = c1*x1+c2*x2
<=> x1 = (V-c2*x2)/2
And just keep incrementing x2 would find me all my x1's.
Which works perfectly for two numbers. I thought I was almost done

First of, I would need to keep all the values actually, because part of the idea is to compare bottom up (iterative) method with top down (recursive) method by comparing the amount of cells used in the array.
Well, I get your tree.
I think I get your pseudocode too. But I'm a bit tired and would try again tomorrow, my brain is slowly shutting down.
Tomorrow or Monday I would also need to build up an array that stores all the solutions and knows how many coins were used arg !
Would you believe that last week's task was to just do the Fibonacci sequence in a few ways ?
|
|
All times are GMT +2. The time now is 02:51.

