SimpleAddition Program

[SrgjanLDTeam]

but i guess its not that simple like the title says :D

ok .. im doing a excercize but im stuck here ..

the excersize sounds like this:
-You are given N coins of value 3 and M coins of value 5.
-Return the smallest sum,
-strictly greater than X that you can achieve by summing up some
-(not necessarily all) of the coins.
If it's not possible to get a number larger than X return -1.

my code:
coin1 is const int == 3;
coin2 is const int == 5;

int CoinAddition(int n, int m, int x){
	int fr = 0;       // function result

	if((n*coin1)+(m*coin2) <= x){
		return -1;
	}else{
		while(fr <= x){
			if(n > 0){
				if(coin2 * 2 >= x && m > 1){
					fr += coin2 * 2;
					m -= 2;
				}else{
					fr += coin1;
					n -= 1;
				}
			}else if(m > 0){
				fr += coin2;
				m -= 1;
			}
			else break;
		} // end of while
		return fr;
	}
} // end of functionj 

my problem:
the problem only works as you can see first by adding 3 ..
so if i have 2 coins of value 3 and 3 coins of value 5 and i put value to achive greater than 14 .. i get result of 16 instead of 15..

the program works like it should right now but..

somehow i need to make the program to choose which coin to add to the sum .. but how ..

because 2x3 = 6 + 5 = 11 + 5 = 16;
what i want to achive is 14 so its easier .. 3 x 5 = 15
15 > 14 and < 16
16 > 14 and > 15

so ... how?

[SrgjanLDTeam]

bump :'(

[Codermik]

So you say, get 6 coins at value 3 (18) and 10 coins at value 5 (50), you need the program to tell you what value is smallest?

[SrgjanLDTeam]

using the coins entered in that case total of value 68.. to find smallest sum that its entered by the user in variable X.. for example

Enter how many coins you have with value of 3: input = 2;
Enter how many coins you have with value of 5: input = 3;
The value you want to achieve is greater than?: input = 14;

in this case the program should do 3x5 .. not 2x3+2x5 .. because 3x5 is the smallest sum that is greater than 14..

[SrgjanLDTeam]

bump ...

[Duthomhas]

This is a permutations problem.

Given, for example, N=3 '3's and M=2 '5's:

3 3 3 5 5

Here are the sums you can get from this permutation:

 0 = 
 3 = 3
 6 = 3 3
 9 = 3 3 3
14 = 3 3 3 5
19 = 3 3 3 5 5

We'll change the permutation by one:

3 3 5 3 5

Now here are our new sums:

 0 = 
 3 = 3
 6 = 3 3
11 = 3 3 5
14 = 3 3 5 3
19 = 3 3 5 3 5

Our complete list of possible sums is now: 0, 3, 6, 9, 11, 14, 19.

See how it works?

(Obnoxious, isn't it?)

Hope this helps.

[SrgjanLDTeam]

well im thking the same thing .. but i cannot convert that algorithm to function :// what if user wants greater than 4? that it will be only 5 not 6 like you mentionet using 2 coins of 3.. if >4 than only coin of 5 .. but thats the problem .. how to invent it in program ://

[SrgjanLDTeam]

bump... :((

[Duthomhas]

Okay, so the program looked fun and I wrote it earlier. Here's a run:

D:\prog\foo> a
How many 3's? 3
How many 5's? 2
What is minimum sum (X+1)? 4
Sums are: 0 3 5 6 8 9 10 11 13 14 16 19
Minimum sum: 5

D:\prog\foo> 

Notice that 5 is in all the sums? That's because the list of 3 3 3 5 5 includes two fives. Choose one of them and you get a sum of... 5.

(My program interface differs a little from yours because I don't ask for X, I ask for X+1. So my entering 4 is the same as entering 3 for X. Otherwise the program runs identically to your problem statement.)


For every possible permutation of the numbers, you get a new possibility of adding stuff together. Once you get the complete list of sums (which for my test case of N=3 and M=2 is 0 3 5 6 8 9 10 11 13 14 16 19) then you can simply find the first number larger than X.


You can generate the list (or, more accurately, the set of sums) using a nested loop, adding numbers along the way. Think about it. (This problem is really an algorithms course kind of question.)

If you don't care to keep the set of numbers, either, you can also just store the smallest number generated so far greater than X.

(My program used some C++11 stuff: next_permutation() and std::set<unsigned>. I may rewrite it now to do with just loops...)

[SrgjanLDTeam]

alright sorry than :/ i didnt get that ..

[Duthomhas]

Holy crap, that was easier than I thought. And much faster than next_permutation(), of course.

Your nested loop only need be three or four lines long, not counting vertical whitespace and braces.

[SrgjanLDTeam]

ok :|

[Duthomhas]

What level course are you taking? Tell me 250 at least, right?

Because if this is an intro to CS course then your instructor is a jerk.



Calculate EVERY POSSIBLE SUM.

Given 3 3 3 5 5 (that's 3 threes and 2 fives):

(3 * 0) + (5 * 0) = 0
(3 * 0) + (5 * 1) = 5
(3 * 0) + (5 * 2) = 10

(3 * 1) + (5 * 0) = 3
(3 * 1) + (5 * 1) = 8
(3 * 1) + (5 * 2) = 13

(3 * 2) + (5 * 0) = 6
(3 * 2) + (5 * 1) = 11
(3 * 2) + (5 * 2) = 16

(3 * 3) + (5 * 0) = 9
(3 * 3) + (5 * 1) = 14
(3 * 3) + (5 * 2) = 19

What is the smallest sum larger than X?

X= 1 --> 3
X=19 --> none --> -1
X=11 --> 13
X=10 --> 11

Watch the patterns. Write the loops. Build the list. Choose the smallest number from the list greater than X.

Good luck!

[Drrockso]

I have to ask. What is bump?

[Duthomhas]

Every time someone replies to a thread it is moved (or "bumped") to the top of the list of current threads. Sometimes an OP will be too impatient to wait a day for someone to help, so will artificially "bump" his/her thread to the top with "bump" posts.

Bumps are only, IMHO, appropriate after a couple of days when it appears that OP's post was lost in a flurry of posting. If no one replies after that, it means no one knows how to help (or possibly no one cares to help).