C++ help

[davy.zou@brentwood.bc.ca]

I have started learning c++ and I need help. I need to write a
program, the question is as follows.

At a post office, there are a certain number of 2, 7, and 9cents
stamps, now, given a total number of cents required, find the correct
and most effective combination of stamps.

meaning that if you were to need 14cents, the correct output should be
2 seven cents not 7 two cents.

the program is to use functions, and at first I thought I could use
bisection searching, but that didn't go very well. I think we are
suppose to use call-by-references as well, except I haven't figured
out how to do that yet.

Any help would be greatly appreciated.

Thanks
Davy

[Ian Collins]

Re: C++ help

davy.zou@brentw ood.bc.ca wrote:

I have started learning c++ and I need help. I need to write a
program, the question is as follows.
>
At a post office, there are a certain number of 2, 7, and 9cents
stamps, now, given a total number of cents required, find the correct
and most effective combination of stamps.
>
meaning that if you were to need 14cents, the correct output should be
2 seven cents not 7 two cents.
>
the program is to use functions, and at first I thought I could use
bisection searching, but that didn't go very well. I think we are
suppose to use call-by-references as well, except I haven't figured
out how to do that yet.
>
Any help would be greatly appreciated.
>

Post an attempt and you will get some help. We don't do homework here,
but we are happy to help with problems in your homework code.

--
Ian Collins.

[davy.zou@brentwood.bc.ca]

Re: C++ help

On Mar 3, 5:55 pm, Ian Collins <ian-n...@hotmail.co mwrote:

davy....@brentw ood.bc.ca wrote:

I have started learning c++ and I need help. I need to write a
program, the question is as follows.

>

At a post office, there are a certain number of 2, 7, and 9cents
stamps, now, given a total number of cents required, find the correct
and most effective combination of stamps.

>

meaning that if you were to need 14cents, the correct output should be
2 seven cents not 7 two cents.

>

the program is to use functions, and at first I thought I could use
bisection searching, but that didn't go very well. I think we are
suppose to use call-by-references as well, except I haven't figured
out how to do that yet.

>

Any help would be greatly appreciated.

>
Post an attempt and you will get some help. We don't do homework here,
but we are happy to help with problems in your homework code.
>
--
Ian Collins.

I wasn't asking anyone to do my homework. I just need someone to point
me in the right direction.

[davy.zou@brentwood.bc.ca]

Re: C++ help

here is the code I first came up with, obviously it doesn't work,

#include <iostream.h>
#include <math.h>


int centscalculatio n (int x, int y, int z);
int computecent (int x, int y, int z);

int centscalculatio n (int x, int y, int z) {
double low=0, high=1, guessedcent, calculatedcent;
const double epsilon=0.0001;

for (;;) {
guessedcent=(lo w+high)/2;
if ((high-low)<(2*epsilon )) {
return guessedcent;
}

centscalculatio n=computecent (x, y, z);

if (calculatedcent ==guessedcent) {
return guessedcent;
}

if (calculatedcent >guessedcent) {
low=guessedcent ;
} else {
high=guessedcen t;
}
}


}

int computecent (int x, int y, int z) {

int a=2, b=7, c=9;


return x*a+y*b+z*c;

}



void main () {

int cents, a=2, b=7, c=9, x, y, z, ans; //a has value of 2, b has 7,
c has 9

while (true) {

cout<<"Enter cents, 0 to terminate: "<<endl;
cin>>cents;

if (cents<0) {
cout<<"Error."< <endl;
}

if (cents=0) {
break;
}


ans=centscalcul ation (x, y, z);

cout<<"answer is "<<ans<<end l;
}


}

[Gavin Deane]

Re: C++ help

On 3 Mar, 23:02, davy....@brentw ood.bc.ca wrote:

On Mar 3, 5:55 pm, Ian Collins <ian-n...@hotmail.co mwrote:

davy....@brentw ood.bc.ca wrote:

I have started learning c++ and I need help. I need to write a
program, the question is as follows.

>

At a post office, there are a certain number of 2, 7, and 9cents
stamps, now, given a total number of cents required, find the correct
and most effective combination of stamps.

>

meaning that if you were to need 14cents, the correct output should be
2 seven cents not 7 two cents.

>

the program is to use functions, and at first I thought I could use
bisection searching, but that didn't go very well. I think we are
suppose to use call-by-references as well, except I haven't figured
out how to do that yet.

>

Any help would be greatly appreciated.

>

Post an attempt and you will get some help. We don't do homework here,
but we are happy to help with problems in your homework code.

I wasn't asking anyone to do my homework. I just need someone to point
me in the right direction.

The FAQ is at http://www.parashift.com/c++-faq-lite/ but it seems to
be down at the moment. When it comes back to life, the FAQ you want is
5.8. As Ian says, there are plenty of people here willing and able to
help you, but none of them are mind-readers. Nobody can help you
without knowing what your problem is. FAQ 5.8 explains how to get that
help. In summary:

Post the actual code you are having problems with, not a description
of the code.
Post *minimal* code - i.e. the *smallest possible* program that
exhibits your problem.
Post *compileable* code - i.e. copied and pasted *directly* from your
editor into your message
For code that does not compile and you don't understand why, copy and
past the error messages directly from your compiler and make it clear
which statement(s) the error refers to.
For a program that compiles and runs but doesn't behave as you expect,
post the inputs to the program, the actual outputs and your expected
outputs.

Without all this, nobody can be sure they are recreating exactly the
situation you have and be sure they are answering the right question.

HTH
Gavin Deane

[davy.zou@brentwood.bc.ca]

Re: C++ help

On Mar 3, 6:23 pm, "Gavin Deane" <deane_ga...@ho tmail.comwrote:

On 3 Mar, 23:02, davy....@brentw ood.bc.ca wrote:
>
>
>

On Mar 3, 5:55 pm, Ian Collins <ian-n...@hotmail.co mwrote:

davy....@brentw ood.bc.ca wrote:
I have started learning c++ and I need help. I need to write a
program, the question is as follows.

>

At a post office, there are a certain number of 2, 7, and 9cents
stamps, now, given a total number of cents required, find the correct
and most effective combination of stamps.

>

meaning that if you were to need 14cents, the correct output should be
2 seven cents not 7 two cents.

>

the program is to use functions, and at first I thought I could use
bisection searching, but that didn't go very well. I think we are
suppose to use call-by-references as well, except I haven't figured
out how to do that yet.

>

Any help would be greatly appreciated.

>

Post an attempt and you will get some help. We don't do homework here,
but we are happy to help with problems in your homework code.

I wasn't asking anyone to do my homework. I just need someone to point
me in the right direction.

>
The FAQ is athttp://www.parashift.c om/c++-faq-lite/but it seems to
be down at the moment. When it comes back to life, the FAQ you want is
5.8. As Ian says, there are plenty of people here willing and able to
help you, but none of them are mind-readers. Nobody can help you
without knowing what your problem is. FAQ 5.8 explains how to get that
help. In summary:
>
Post the actual code you are having problems with, not a description
of the code.
Post *minimal* code - i.e. the *smallest possible* program that
exhibits your problem.
Post *compileable* code - i.e. copied and pasted *directly* from your
editor into your message
For code that does not compile and you don't understand why, copy and
past the error messages directly from your compiler and make it clear
which statement(s) the error refers to.
For a program that compiles and runs but doesn't behave as you expect,
post the inputs to the program, the actual outputs and your expected
outputs.
>
Without all this, nobody can be sure they are recreating exactly the
situation you have and be sure they are answering the right question.
>
HTH
Gavin Deane

Thanks alot.

[osmium]

Re: C++ help

<davy.zou@brent wood.bc.cawrote :

here is the code I first came up with, obviously it doesn't work,

<snip>

Think about dividing the available amount by 9, 7 and 2 in that order. I am
not sure that is the right answer in all cases, but you can expand on it if
needed. Look up the modulo operator (%). See the Wikipedia entry for
modulo..

[davy.zou@brentwood.bc.ca]

Re: C++ help

On Mar 3, 6:43 pm, "osmium" <r124c4u...@com cast.netwrote:

<davy....@brent wood.bc.cawrote :

here is the code I first came up with, obviously it doesn't work,

>
<snip>
>
Think about dividing the available amount by 9, 7 and 2 in that order. I am
not sure that is the right answer in all cases, but you can expand on it if
needed. Look up the modulo operator (%). See the Wikipedia entry for
modulo..

THANK YOU! dividing it by 9, 7, and 2! that is ingenious!

[Kai-Uwe Bux]

Re: C++ help

osmium wrote:

<davy.zou@brent wood.bc.cawrote :
>

>here is the code I first came up with, obviously it doesn't work,

>
<snip>
>
Think about dividing the available amount by 9, 7 and 2 in that order. I
am not sure that is the right answer in all cases, but you can expand on
it if needed. [snip]

I am not so sure that this looks like a promissing line of attack. There
seems to be a little more to the problem. What is the answer for 10 and how
do you find it through the division sequence? What about 35?


Best

Kai-Uwe Bux

[bnonaj]

Re: C++ help

davy.zou@brentw ood.bc.ca wrote:

I have started learning c++ and I need help. I need to write a
program, the question is as follows.
>
At a post office, there are a certain number of 2, 7, and 9cents
stamps, now, given a total number of cents required, find the correct
and most effective combination of stamps.
>
meaning that if you were to need 14cents, the correct output should be
2 seven cents not 7 two cents.
>
the program is to use functions, and at first I thought I could use
bisection searching, but that didn't go very well. I think we are
suppose to use call-by-references as well, except I haven't figured
out how to do that yet.
>
Any help would be greatly appreciated.
>
Thanks
Davy
>

This is a variation of the bin packing problem. I've developed
C++ code which can solve this problem for all solutions. It is
also capable of handling target ranges as well, and multiples
thereof. It's known to be a hard problem to create an efficient
algorithm for.

JB

[Kai-Uwe Bux]

Re: C++ help

davy.zou@brentw ood.bc.ca wrote:

On Mar 3, 5:55 pm, Ian Collins <ian-n...@hotmail.co mwrote:

>davy....@brent wood.bc.ca wrote:

I have started learning c++ and I need help. I need to write a
program, the question is as follows.

>>

At a post office, there are a certain number of 2, 7, and 9cents
stamps, now, given a total number of cents required, find the correct
and most effective combination of stamps.

>>

meaning that if you were to need 14cents, the correct output should be
2 seven cents not 7 two cents.

>>

the program is to use functions, and at first I thought I could use
bisection searching, but that didn't go very well. I think we are
suppose to use call-by-references as well, except I haven't figured
out how to do that yet.

>>

Any help would be greatly appreciated.

>>
>Post an attempt and you will get some help. We don't do homework here,
>but we are happy to help with problems in your homework code.
>>
>--
>Ian Collins.

>
I wasn't asking anyone to do my homework. I just need someone to point
me in the right direction.

The following three observations might prove useful:

a) You shall never need to use more than 6 stamps of 2c because you can
trade 7 stamps of 2c for 2 stamps of 7c.

b) You shall never need to use more than 8 stamps of 7c because you can
trade 9 stamps of 7c for 7 stamps of 9c.

c) You shall never need to use both 7c and 2c stamps because you can trade a
pair of a 7c stamp and a 2c stamp for a single 9c stamp.


This cuts down the complexity of the problem to a managable size.


Best

Kai-Uwe Bux

[untitled]

Re: C++ help

ok for number 19 for example, we can use 9+2+2+2+2+2 as effective in
terms of cost, but also 9+9 is more effective in terms of number of
stamps but we will waste 1 cent.

which one we should use? i need to understand the problem first to
solve it.

[untitled]

Re: C++ help

with number 3, 5 we will waste one cent, not an option, so can we
tolerent loosing one cent at higher numbers like 22?
so 22cents = 7+7+7 and waste one cent, instead of 9+9+2+2 more stamps
but waste nothing.

[davy.zou@brentwood.bc.ca]

Re: C++ help

On Mar 3, 8:43 pm, "untitled" <awsra...@gmail .comwrote:

ok for number 19 for example, we can use 9+2+2+2+2+2 as effective in
terms of cost, but also 9+9 is more effective in terms of number of
stamps but we will waste 1 cent.
>
which one we should use? i need to understand the problem first to
solve it.

You use the one with the least number of stamps. and if you run into a
number like 35, you use 36cents as the ans. So you go one above the
required number.

[Alan Johnson]

Re: C++ help

davy.zou@brentw ood.bc.ca wrote:

I have started learning c++ and I need help. I need to write a
program, the question is as follows.
>
At a post office, there are a certain number of 2, 7, and 9cents
stamps, now, given a total number of cents required, find the correct
and most effective combination of stamps.
>
meaning that if you were to need 14cents, the correct output should be
2 seven cents not 7 two cents.
>
the program is to use functions, and at first I thought I could use
bisection searching, but that didn't go very well. I think we are
suppose to use call-by-references as well, except I haven't figured
out how to do that yet.
>
Any help would be greatly appreciated.
>
Thanks
Davy
>

This is a classic dynamic programming problem. Let's start by laying
some foundation you'll need to develop a solution.

Let's say you already have a solution for N cents. For example, if
N=23, the solution would be {9, 7, 7}. The first thing you should
notice is that the solution has what is called an "optimal
substructure". That is, if you took any part of the solution, it is
optimal for smaller version of the problem. From the example N=23, we
have subsolutions {9, 7} and {7, 7}, which are optimal for N=16 and
N=14, respectively. It is trivial to prove by contradiction that the
optimal substructure property holds for every solution. I'll leave that
as an exercise for you, or you can just assume I'm right.

So, the goal is to find the fewest number of stamps needed to make some
value. Let's call that C(N). Examples: C(23) = 3, C(14) = 2, C(16) = 2.
Because of optimal substructure, we know that the solution for C(N) is
the same as some smaller problem plus one more stamp. That is, it is
either 1+C(N-2), or 1+C(N-7), or 1+C(N-9). How do we decide which one?
Easy, we compute them all, and use the smallest, since we are trying to
minimize the number of stamps.

Combine this with the fact that the solution for N=0 is obviously 0
stamps, and you get the following recursion:

C(N) = 0 if N = 0
C(N) = min( 1+C(N-2), 1+C(N-7), 1+C(N-9) ) if N 0


Now all you need to do is write some C++ code that implements that
recursion. (Hint: Make an array of size N, and make a loop that computes
all the solutions from i=0 to i=N. At any particular i, you should
already have the recursive values computed.)

--
Alan Johnson