Programming question (algorithm) - RPGWatch Forums
|
Your donations keep RPGWatch running!
RPGWatch Forums » General Forums » Off-Topic » Programming question (algorithm)

Default 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.
Pladio is offline

Pladio

Pladio's Avatar
Guardian of Nonsense
RPGWatch Donor
Original Sin Donor

#1

Join Date: Nov 2006
Location: Manchester, United Kingdom
Posts: 7,893
Mentioned: 80 Post(s)

Default 

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
GothicGothicness is offline

GothicGothicness

GothicGothicness's Avatar
SasqWatch

#2

Join Date: Oct 2006
Posts: 6,233
Mentioned: 12 Post(s)

Default 

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 ?
Pladio is offline

Pladio

Pladio's Avatar
Guardian of Nonsense
RPGWatch Donor
Original Sin Donor

#3

Join Date: Nov 2006
Location: Manchester, United Kingdom
Posts: 7,893
Mentioned: 80 Post(s)

Default 

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

GothicGothicness

GothicGothicness's Avatar
SasqWatch

#4

Join Date: Oct 2006
Posts: 6,233
Mentioned: 12 Post(s)

Default 

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--
}
Pladio is offline

Pladio

Pladio's Avatar
Guardian of Nonsense
RPGWatch Donor
Original Sin Donor

#5

Join Date: Nov 2006
Location: Manchester, United Kingdom
Posts: 7,893
Mentioned: 80 Post(s)

Default 

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:

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);
}
ecliptic is offline

ecliptic

Traveler

#6

Join Date: Mar 2011
Posts: 5
Mentioned: 0 Post(s)

Default 

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.
hishadow is offline

hishadow

Level N+1

#7

Join Date: Mar 2008
Location: Scandinavia
Posts: 1,163
Mentioned: 1 Post(s)

Default 

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.
Thrasher is offline

Thrasher

Thrasher's Avatar
Wheeee!

#8

Join Date: Aug 2008
Location: Studio City, CA
Posts: 15,603
Mentioned: 16 Post(s)

Default 

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
HiddenX is offline

HiddenX

HiddenX's Avatar
The Elder Spy
RPGWatch Team
Original Sin 1 & 2 Donor

#9

Join Date: Oct 2006
Location: NRW/Germany
Posts: 15,147
Mentioned: 123 Post(s)

Default 

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
Pladio is offline

Pladio

Pladio's Avatar
Guardian of Nonsense
RPGWatch Donor
Original Sin Donor

#10

Join Date: Nov 2006
Location: Manchester, United Kingdom
Posts: 7,893
Mentioned: 80 Post(s)

Default 

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
Last edited by Pladio; March 25th, 2011 at 02:13.
Pladio is offline

Pladio

Pladio's Avatar
Guardian of Nonsense
RPGWatch Donor
Original Sin Donor

#11

Join Date: Nov 2006
Location: Manchester, United Kingdom
Posts: 7,893
Mentioned: 80 Post(s)

Default 

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…

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

GothicGothicness

GothicGothicness's Avatar
SasqWatch

#12

Join Date: Oct 2006
Posts: 6,233
Mentioned: 12 Post(s)

Default 

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.
ecliptic is offline

ecliptic

Traveler

#13

Join Date: Mar 2011
Posts: 5
Mentioned: 0 Post(s)

Default 

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…
Pladio is offline

Pladio

Pladio's Avatar
Guardian of Nonsense
RPGWatch Donor
Original Sin Donor

#14

Join Date: Nov 2006
Location: Manchester, United Kingdom
Posts: 7,893
Mentioned: 80 Post(s)

Default 

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.
ecliptic is offline

ecliptic

Traveler

#15

Join Date: Mar 2011
Posts: 5
Mentioned: 0 Post(s)

Default 

March 19th, 2011, 14:42
Originally Posted by GothicGothicness View Post
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…

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) ?
Pladio is offline

Pladio

Pladio's Avatar
Guardian of Nonsense
RPGWatch Donor
Original Sin Donor

#16

Join Date: Nov 2006
Location: Manchester, United Kingdom
Posts: 7,893
Mentioned: 80 Post(s)

Default 

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.
Pladio is offline

Pladio

Pladio's Avatar
Guardian of Nonsense
RPGWatch Donor
Original Sin Donor

#17

Join Date: Nov 2006
Location: Manchester, United Kingdom
Posts: 7,893
Mentioned: 80 Post(s)

Default 

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
Last edited by Pladio; March 25th, 2011 at 02:13.
Pladio is offline

Pladio

Pladio's Avatar
Guardian of Nonsense
RPGWatch Donor
Original Sin Donor

#18

Join Date: Nov 2006
Location: Manchester, United Kingdom
Posts: 7,893
Mentioned: 80 Post(s)

Default 

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:

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 Pladio View Post
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!):



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!
VPeric is offline

VPeric

Sentinel

#19

Join Date: Oct 2006
Location: Serbia
Posts: 585
Mentioned: 0 Post(s)

Default 

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 ?
Pladio is offline

Pladio

Pladio's Avatar
Guardian of Nonsense
RPGWatch Donor
Original Sin Donor

#20

Join Date: Nov 2006
Location: Manchester, United Kingdom
Posts: 7,893
Mentioned: 80 Post(s)
RPGWatch Forums » General Forums » Off-Topic » Programming question (algorithm)

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

All times are GMT +2. The time now is 02:51.
Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, vBulletin Solutions Inc.
vBulletin Security provided by DragonByte Security (Pro) - vBulletin Mods & Addons Copyright © 2022 DragonByte Technologies Ltd.
User Alert System provided by Advanced User Tagging (Lite) - vBulletin Mods & Addons Copyright © 2022 DragonByte Technologies Ltd.
Copyright by RPGWatch