C++ help

[davy.zou]

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]

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.

 

[davy.zou]

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.

 

[davy.zou]

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

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


int centscalculation (int x, int y, int z);
int computecent (int x, int y, int z);

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

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

centscalculation=computecent (x, y, z);

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

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


}

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=centscalculation (x, y, z);

cout<<"answer is "<<ans<<endl;
}


}

 

[Gavin Deane]

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]

The FAQ is athttp://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

Thanks alot.

 

[osmium]

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

 

[Kai-Uwe Bux]

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

 

[davy.zou]

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

 

[bnonaj]

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]

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]

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]

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]

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]

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

 

[untitled]

ok here is my idea, it gives 1cent below the required number,

x is the required number

int sevens=x/7 //without the fractures
remainder = x-(sevens*7)
int twos= remainder/2 //without fractures
uint nines=sevens-twos //without sign
sevens=sevens-nines
twos=twos-nines

print nines,sevens,twos

i'll write the one with one above the required number in few minutes...

 

[untitled]

then its an easy one,

x is the requested number


int sevens=x/7 //without the fractures
remainder=x - (sevens*7)
int twos= remainder/2 //without the fractures
if (remainder - (twos*2)) =1 then twos++
if sevens != 0 && sevens<twos then twos=twos-sevens, nines= sevens,
sevens=0
if twos != 0 && twos<sevens then sevens=sevens-twos, nines= twos, twos
=0

just put it in c code

 

[Alan Johnson]

then its an easy one,

x is the requested number


int sevens=x/7 //without the fractures
remainder=x - (sevens*7)
int twos= remainder/2 //without the fractures
if (remainder - (twos*2)) =1 then twos++
if sevens != 0 && sevens<twos then twos=twos-sevens, nines= sevens,
sevens=0
if twos != 0 && twos<sevens then sevens=sevens-twos, nines= twos, twos
=0

just put it in c code

Judging from the OP's description, this is an assignment for some sort
of algorithms class. If that's the case, then coming up with a solution
that actually depends on the number 2, 7, and 9 isn't particularly useful.

How would you solve the problem if the denominations were D1, D2, and
D3, rather than some specific three numbers? Or better yet, let's say
you have denominations D1 through Dk.

 

[davy.zou]

Judging from the OP's description, this is an assignment for some sort
of algorithms class. If that's the case, then coming up with a solution
that actually depends on the number 2, 7, and 9 isn't particularly useful.

How would you solve the problem if the denominations were D1, D2, and
D3, rather than some specific three numbers? Or better yet, let's say
you have denominations D1 through Dk.

It is not an algorithm class, it is purely C++, we get to algorithms
next year, I think.
But you have peaked my interest, would D1 through Dk be inputed by
user? If it is inputed by user, then it shouldn't be too difficult to
add the lines of codes to the program that will assign the user input
to D1 through Dk.

Davy

 

[davy.zou]

then its an easy one,

x is the requested number

int sevens=x/7 //without the fractures
remainder=x - (sevens*7)
int twos= remainder/2 //without the fractures
if (remainder - (twos*2)) =1 then twos++
if sevens != 0 && sevens<twos then twos=twos-sevens, nines= sevens,
sevens=0
if twos != 0 && twos<sevens then sevens=sevens-twos, nines= twos, twos
=0

just put it in c code

1 1int sevens=x/7 //without the
fractures
2 remainder=x - (sevens*7)
3 int twos= remainder/2 //without the fractures
4 if (remainder - (twos*2)) =1 then twos++
5 if sevens != 0 && sevens<twos then twos=twos-sevens, nines= sevens,
sevens=0
6 if twos != 0 && twos<sevens then sevens=sevens-twos, nines= twos,
twos=0

I don't get it. Several things in fact.

First, I can't see what your program does. Since it doesn't have an
output statement. But I will go on a tangent and guess that it is for
comparing which ever way is the most effective way to distribute the
stamps.

Second, why not just use x%7 for line 2?

Third, since you assigned that twos be reminder/2, then the act of
mutiplying twos by 2 would result in the remainder from line2.
Therefore, in line4, having remainder-remainder would result in 0.

Fourth, in line4, what do you mean by twos++?

Five, line 5 and 6 doesn't make much sense either.

Six, what is if final out put?

I really appreciate you trying to help, and I know that with the above
list I sound like an ungrateful little brat. But I am grateful. I just
don't get your programing. Please explain.

Davy