Programming question (algorithm)

Pladio

Guardian of Nonsense
Staff Member
Moderator
Original Sin Donor
Joined
November 13, 2006
Messages
9,177
Location
Manchester, United Kingdom
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.
 
Joined
Nov 13, 2006
Messages
9,177
Location
Manchester, United Kingdom
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 :D
 
Joined
Oct 25, 2006
Messages
6,292
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 ?
 
Joined
Nov 13, 2006
Messages
9,177
Location
Manchester, United Kingdom
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.
 
Joined
Oct 25, 2006
Messages
6,292
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--
}
 
Joined
Nov 13, 2006
Messages
9,177
Location
Manchester, United Kingdom
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:

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);
}
 
Joined
Mar 8, 2011
Messages
5
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.
 
Joined
Mar 30, 2008
Messages
1,163
Location
Scandinavia
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.
 
Joined
Aug 18, 2008
Messages
15,679
Location
Studio City, CA
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
 
Joined
Oct 18, 2006
Messages
19,828
Location
Germany
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 :)
 
Joined
Nov 13, 2006
Messages
9,177
Location
Manchester, United Kingdom
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
 
Last edited:
Joined
Nov 13, 2006
Messages
9,177
Location
Manchester, United Kingdom
Again, do it recursively instead. I would start over ( especially you should know if you use goto you're going the wrong way :p 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);
}

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.
 
Joined
Oct 25, 2006
Messages
6,292
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.
 
Joined
Mar 8, 2011
Messages
5
I guess as long as you're systemic about how you change coin sizes it won't be an issue.
 
Joined
Mar 8, 2011
Messages
5
Again, do it recursively instead. I would start over ( especially you should know if you use goto you're going the wrong way :p 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);
}

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.

GG, what's coinslength in your code ? And add(sol,coins[0]) ? and remove (coins,0) ?
 
Joined
Nov 13, 2006
Messages
9,177
Location
Manchester, United Kingdom
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
 
Last edited:
Joined
Nov 13, 2006
Messages
9,177
Location
Manchester, United Kingdom
Pladio, first of all, your code will not generalize to more than 2 coins, so don't even try. :D 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);
}

GG, what's coinslength in your code ? And add(sol,coins[0]) ? and remove (coins,0) ?

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

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!):

changegraph.png


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++):

Code:
int calculate(int[] coins, int value){
  if (value < 0)
    return 0; //no solution
  if (value == 0)
    return 1; //it's one solution
  int solutions = 0; 
  for (int i = coins.length; int > 0; i—){ //for every coin we can use, starting from the last (ie. largest)
    solutions += calculate(coins, value - coins[i]);
    coins.remove(i); //remove the i-th, that is, the biggest coin from the list
}
  return solutions;
}

The key part here is the for cycle - it assures that we don't use larger coins than the ones we already used, which eliminates the problem of duplication (of course, it also assures us that we will try all possible combinations). I assume that in your language, when you call calculate again the array will be copied by value, not by reference (so not just the pointer, ie. not a shallow copy); if not, you ought to assure that'll happen.

Hope that helps! :)
 
Joined
Oct 23, 2006
Messages
585
Location
Serbia
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 ?
 
Joined
Nov 13, 2006
Messages
9,177
Location
Manchester, United Kingdom
Back
Top Bottom