CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Junior Member
Join Date
Dec 2012
Posts
3

nested for loops

hi,

i am currently trying to teach my self c++. Workign fin so far, but now i have hit a break with this problem:
(translated by me, sorry)

1) you are given a large number x and a subset of smaller numbers a<b<c<d. Find the smallest amount of a,b,c,d possible to reach x.
So you are supposed to find a combination like "5*a + 3*b + 1*d" == x, where 5+3+1 is the smallest possible.

I would have otped for bruteforce testing all possible combinations, but the book says no bruteforcing.

The example is taken from the "advanced" part of my book, chapter "loops and algorithms". A solution is supposed to be on an accompanying cd, but i lost that ages ago.

any hints for me?

p.s. coudlnt think of a proper title, sorry...

2. Elite Member Power Poster
Join Date
Nov 2003
Location
Florida
Posts
12,518

Re: nested for loops

Sounds like a pretty typical exercise. Forgetting programming for a minute, how would you do it with a pencil and paper.

Let's say the number is 55, and the smaller numbers are 1, 2, 3, 4. What steps would you take to solve it? Once you can answer that, then you can figure out how to code it. To give you a clue, the solution uses division and remainders.

3. Junior Member
Join Date
Dec 2012
Posts
3

Re: nested for loops

i do not know.
The straight forward approach would be:

1) a = x/a;
2) b = (x%a)/b
3) c = ((x%a)%c)/d
...

But that doesnt work, as you have to be able to "undo" the algorithm, when you find that there`s leftover at the end (assuming there is no a,b,c,d == 1).
Also, wired numbers may have "exceptions", no? Where above algorithm will miss the optimal solution. (although i couldnt think of an example right now, i ll keep trying )

if it`s a typical exercise, do you know of a tutorial or exemplary solution? I am still sort of clueless and wasnt able to find anything. :S

4. Elite Member Power Poster
Join Date
Apr 2000
Location
Belgium (Europe)
Posts
4,626

Re: nested for loops

a recursive or backtracking algorithm seems like the obvious first approach i'd go for.

From a pure mathematical p.o.v. I don't think there is method for solving this (it's a fitting problem), and that means brute forcing.

Of course there are gradients in what you consider "brute force". A recursive or backtracking solution would just be "smart" approaches to brute forcing (you attempt to try the most likely solutions first), but in a worst case scenario, you could be ending up trying every possible combination anyway.
The fact it is about "loops and algorithms", would lead me to believe the idea is in fact to try a backtracking approach.

You didn't mention the title of the book.
Most book publishers, or the authors host accompanying cd's/disks on their website.
Even if they don't, someone else that bought the book may have the disk on his website.

5. Elite Member Power Poster
Join Date
Apr 1999
Posts
27,449

Re: nested for loops

Originally Posted by skidrive
1) you are given a large number x and a subset of smaller numbers a<b<c<d. Find the smallest amount of a,b,c,d possible to reach x.
So you are supposed to find a combination like "5*a + 3*b + 1*d" == x, where 5+3+1 is the smallest possible.
Let me try to rephrase this with a real life problem:

A country (USA) has coins in the denonimation of 1 cent, 5 cents, 10 cents, 25 cents, 50 cents. It takes 100 cents to make 1 dollar. What is the least number of coins needed to equal a certain dollar and cents amount?

In other words, you have 5 coin types, so what is the least amount of coins you would need jingling in your pocket to equal, say 5 dollars and 30 cents? Or 3 dollars and 10 cents? or no dollars and 75 cents? etc.

If this is not the same problem, then clarify. If it is the same problem, then does this help you visualize more clearly the goal?

Regards,

Paul McKenzie

6. Elite Member Power Poster
Join Date
Apr 2000
Location
Belgium (Europe)
Posts
4,626

Re: nested for loops

An important difference with money is that the currency makers will (usually ) be nice enough to provide us with the 1 coin value.
This means you can solve the problem mathematically without loops, but it may not be optimal. In that approach you would be 'greedy' and assume that you take as much of a bigger coin values as possible and the pass the remainder onto the smaller coins.

No 50 cents fit
No 25 cents fit
1x 10 cents coin fits, leaving 3
No 5 cents fit
3x 1cent fits.
you needed 4 coins.

a simple set of divisions, modulo's and subtractions will solve this.

But it's not guaranteed optimal.
Suppose there existed a 4 cents coin and you needed to get 8 cents total.
Using the 'greedy' approach above, you would end up with 1x 5cents and 3x 1cents. (4 coins)
where the optimal is 2x 4cents (2 coins).

This calculated 'greedy' approach also only has a guaranteed answer if the 1 coin value is present.

In the more generalized problem (as stated in the OP which does not guarantee the presense of 1) there might be no answer from the greedy calculation, even when there is a possible answer.

note that in the absense of 1, some values will not be possible to achieve even with trying all the possibilities.
Last edited by OReubens; December 14th, 2012 at 04:33 AM.

7. Elite Member Power Poster
Join Date
Apr 2000
Location
Belgium (Europe)
Posts
4,626

Re: nested for loops

rereading the OP. This was actually about finding the optimal solution (lowest a+b+c+d), and not about finding a solution.

This actually makes it impossible to solve without going for a brute force approach when you try to break down the large number into it's constituent smaller parts. You will need to try alternative solutions to the first one you find to make sure there are no more optimal ones.

That doesn't mean there's no efficient way to solve this with a computer, if you can afford to spend some memory on it.
The idea is to turn the problem upside down.
Rather than asking "how do I break a large number into the smallest amount of smaller bits".
You turn it upside down into "what large values do I progressively get when I combine smaller bits".

In an algorithm rough outline).
Make an array at least the size of the large number you want to get.
this array needs to have an indicator for "empty", a reference/list of values of what small bits make this value. a count of the number of bits to make this value.
empty the array
start filling the array with all the possible values you can make with 1 'small bit'.
you then combine each of the already filled in answers of count 1, with each of the single values to make all the possible answers of count 2. fill your answer in the array if there's not already an answer there.
repeat to combine all the count 2 answers with each of the single values to make all the possible count 3 answers.
repeat until you have an answer for the larger value you were seeking.

example.
suppose you have numbers 1 4 and 5. And you're looking to find an answer for making 13.
you make an array of size 9.
at index 1 you fill in the answer "1" of count 1
at index 4 you fill in the answer "4" of count 1
at index 5 you fill in the answer "5" of count 1

you then combine all the count 1 answers with all the single values.
index 1 has a count 1, we will combine with all the values
at index 2 we fill in "1+1" of count 2
we ignore "1+4" because we already have a better solution there
at index 6 we fill in "1+5"
index 4 has a count of 1, combine with each of the values
we ignore 4+1 already have a 5
at index 8 we fill in "4+4"
at index 9 we fill in "4+5"
index 5 has a count of 1, combine with each of the values
we ignore 5+1 already have a 6
we ignore 5+4 already have a 9
at index 10 we fill in "5+5"

next we for-loop over the array finding all the count 2 answers and combining with each of the 3 values.
etc...

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•