By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
457,911 Members | 1,274 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 457,911 IT Pros & Developers. It's quick & easy.

C++ help

P: n/a
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

Mar 3 '07 #1
Share this Question
Share on Google+
45 Replies


P: n/a
da******@brentwood.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.
Mar 3 '07 #2

P: n/a
On Mar 3, 5:55 pm, Ian Collins <ian-n...@hotmail.comwrote:
davy....@brentwood.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.

Mar 3 '07 #3

P: n/a
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;
}
}

Mar 3 '07 #4

P: n/a
On 3 Mar, 23:02, davy....@brentwood.bc.ca wrote:
On Mar 3, 5:55 pm, Ian Collins <ian-n...@hotmail.comwrote:
davy....@brentwood.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

Mar 3 '07 #5

P: n/a
On Mar 3, 6:23 pm, "Gavin Deane" <deane_ga...@hotmail.comwrote:
On 3 Mar, 23:02, davy....@brentwood.bc.ca wrote:
On Mar 3, 5:55 pm, Ian Collins <ian-n...@hotmail.comwrote:
davy....@brentwood.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.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.

Mar 3 '07 #6

P: n/a
<da******@brentwood.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..
Mar 3 '07 #7

P: n/a
On Mar 3, 6:43 pm, "osmium" <r124c4u...@comcast.netwrote:
<davy....@brentwood.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!

Mar 4 '07 #8

P: n/a
osmium wrote:
<da******@brentwood.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
Mar 4 '07 #9

P: n/a
da******@brentwood.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
Mar 4 '07 #10

P: n/a
da******@brentwood.bc.ca wrote:
On Mar 3, 5:55 pm, Ian Collins <ian-n...@hotmail.comwrote:
>davy....@brentwood.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
Mar 4 '07 #11

P: n/a
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.

Mar 4 '07 #12

P: n/a
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.

Mar 4 '07 #13

P: n/a
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.

Mar 4 '07 #14

P: n/a
da******@brentwood.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
Mar 4 '07 #15

P: n/a
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...

Mar 4 '07 #16

P: n/a
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

Mar 4 '07 #17

P: n/a
untitled wrote:
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.

--
Alan Johnson
Mar 4 '07 #18

P: n/a
On Mar 3, 9:54 pm, Alan Johnson <a...@yahoo.comwrote:
untitled wrote:
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.

--
Alan Johnson
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

Mar 4 '07 #19

P: n/a
On Mar 3, 9:39 pm, "untitled" <awsra...@gmail.comwrote:
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

Mar 4 '07 #20

P: n/a
On Mar 3, 9:39 pm, "untitled" <awsra...@gmail.comwrote:
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

Mar 4 '07 #21

P: n/a
On Mar 3, 9:39 pm, "untitled" <awsra...@gmail.comwrote:
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

Mar 4 '07 #22

P: n/a
da******@brentwood.bc.ca wrote:
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
You can expand the recurrence I posted earlier in this thread to any
number of denominations. So if I had an array of denominations d.

C(n) = 0 if n = 0
C(n) = minimum value over all i such that d[i] < n of 1 + C(n - d[i])

If we were to translate this to pseudocode it might look something like:

// n is the number for which we are finding a solution.
// d is an array of denominations.
// k is the number of denominations
// S is an array of index denominations.
Solve(n, d, k)

Allocate arrays C and S of size n

// Base condition of recurrence C(0)
C[0] = 0

// Now compute C(1) through C(n)
for v = 1 to n

// maybe something like std::numeric_limits<unsigned>::max()
min = infinity

// Find the minimum value of 1+C(n-d[i])
for i = 1 to k
if (d[i] <= k)
value = 1 + C[v - d[i]]
if (value < min)
min = value
stamp = i

// Store the results for the next loop.
C[v] = min
S[v] = stamp

return S
The array C holds the minimum count of stamps needed for each value,
which is a necessary piece of information, but not exactly what we want.
The array S keeps up with the index of which denomination stamp we add
at each step. We can use that knowledge to construct the actual set of
stamps with something like:

// n is the number for which we are finding a solution.
// d is an array of denominations.
// S is an array of index denominations.
PrintSet(n, d, S)
while (n 0)
Print S[n]
n = n - d[S[n]]

This works due to the same logic we used to create the array in the
first place. At each step we are just subtracting the denomination that
we decided was necessary to add to the optimal substructure to get the
solution for n.

--
Alan Johnson
Mar 4 '07 #23

P: n/a
Alan Johnson wrote:
da******@brentwood.bc.ca wrote:
>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

You can expand the recurrence I posted earlier in this thread to any
number of denominations. So if I had an array of denominations d.

C(n) = 0 if n = 0
C(n) = minimum value over all i such that d[i] < n of 1 + C(n - d[i])

If we were to translate this to pseudocode it might look something like:

// n is the number for which we are finding a solution.
// d is an array of denominations.
// k is the number of denominations
// S is an array of index denominations.
Solve(n, d, k)

Allocate arrays C and S of size n

// Base condition of recurrence C(0)
C[0] = 0

// Now compute C(1) through C(n)
for v = 1 to n

// maybe something like std::numeric_limits<unsigned>::max()
min = infinity

// Find the minimum value of 1+C(n-d[i])
for i = 1 to k
if (d[i] <= k)
value = 1 + C[v - d[i]]
if (value < min)
min = value
stamp = i

// Store the results for the next loop.
C[v] = min
S[v] = stamp

return S
The array C holds the minimum count of stamps needed for each value,
which is a necessary piece of information, but not exactly what we want.
The array S keeps up with the index of which denomination stamp we add
at each step. We can use that knowledge to construct the actual set of
stamps with something like:

// n is the number for which we are finding a solution.
// d is an array of denominations.
// S is an array of index denominations.
PrintSet(n, d, S)
while (n 0)
Print S[n]
n = n - d[S[n]]
Oops. One small correction. You'd probably like to print the actual
denominations in the set, rather than the indices, so:
Print d[S[n]]
This works due to the same logic we used to create the array in the
first place. At each step we are just subtracting the denomination that
we decided was necessary to add to the optimal substructure to get the
solution for n.

--
Alan Johnson
Mar 4 '07 #24

P: n/a
Alan Johnson wrote:
Alan Johnson wrote:
>da******@brentwood.bc.ca wrote:
>>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

You can expand the recurrence I posted earlier in this thread to any
number of denominations. So if I had an array of denominations d.

C(n) = 0 if n = 0
C(n) = minimum value over all i such that d[i] < n of 1 + C(n - d[i])

If we were to translate this to pseudocode it might look something like:

// n is the number for which we are finding a solution.
// d is an array of denominations.
// k is the number of denominations
// S is an array of index denominations.
Solve(n, d, k)

Allocate arrays C and S of size n

// Base condition of recurrence C(0)
C[0] = 0

// Now compute C(1) through C(n)
for v = 1 to n

// maybe something like std::numeric_limits<unsigned>::max()
min = infinity

// Find the minimum value of 1+C(n-d[i])
for i = 1 to k
if (d[i] <= k)
Gah. One more correction. This should have been:
if (d[i] <= v)

> value = 1 + C[v - d[i]]
if (value < min)
min = value
stamp = i

// Store the results for the next loop.
C[v] = min
S[v] = stamp

return S
The array C holds the minimum count of stamps needed for each value,
which is a necessary piece of information, but not exactly what we
want. The array S keeps up with the index of which denomination stamp
we add at each step. We can use that knowledge to construct the
actual set of stamps with something like:

// n is the number for which we are finding a solution.
// d is an array of denominations.
// S is an array of index denominations.
PrintSet(n, d, S)
while (n 0)
Print S[n]
n = n - d[S[n]]

Oops. One small correction. You'd probably like to print the actual
denominations in the set, rather than the indices, so:
Print d[S[n]]
>This works due to the same logic we used to create the array in the
first place. At each step we are just subtracting the denomination
that we decided was necessary to add to the optimal substructure to
get the solution for n.


--
Alan Johnson
Mar 4 '07 #25

P: n/a
On Mar 4, 5:35 am, davy....@brentwood.bc.ca wrote:
On Mar 3, 9:39 pm, "untitled" <awsra...@gmail.comwrote:
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
you are right, it wasn't clear,

first i'll explain how the program will think then i'll answer your
questions:

first line will count how many 7cent stamp could be afforded with the
money required, of course there will be some extra cents we will
process it in line 2
line 2 will see how many extra cents you have after we got all the
sevens.
line 3 will check how many 2cent stamps can be afforded for that extra
cents
line 4 if the remainder was less than 2 cents (ie. 1 cent) then of
course we will consider it 2cent that is adding one cent over the
required money as you told me.
in line 5,6 we replace every 7cent and 2cent stamp to one 9cent stamp
so we got the most effective number of stamps.
line 5 if the 7c stamps was less than the 2c stamps, then combine all
the sevens with an equivilant number of 2c stamps and replace them
with 9c stamps. then delete the combined 7 and 2c stamps.
line 6 do the same if the twos was more than sevens.

the out put will be
int sevens
int nines
int twos

i'll write the code in few minutes.

Mar 4 '07 #26

P: n/a
On Mar 4, 1:36 pm, "untitled" <awsra...@gmail.comwrote:
On Mar 4, 5:35 am, davy....@brentwood.bc.ca wrote:


On Mar 3, 9:39 pm, "untitled" <awsra...@gmail.comwrote:
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

you are right, it wasn't clear,

first i'll explain how the program will think then i'll answer your
questions:

first line will count how many 7cent stamp could be afforded with the
money required, of course there will be some extra cents we will
process it in line 2
line 2 will see how many extra cents you have after we got all the
sevens.
line 3 will check how many 2cent stamps can be afforded for that extra
cents
line 4 if the remainder was less than 2 cents (ie. 1 cent) then of
course we will consider it 2cent that is adding one cent over the
required money as you told me.
in line 5,6 we replace every 7cent and 2cent stamp to one 9cent stamp
so we got the most effective number of stamps.
line 5 if the 7c stamps was less than the 2c stamps, then combine all
the sevens with an equivilant number of 2c stamps and replace them
with 9c stamps. then delete the combined 7 and 2c stamps.
line 6 do the same if the twos was more than sevens.

the out put will be
int sevens
int nines
int twos

i'll write the code in few minutes.- Hide quoted text -

- Show quoted text -
ok here is the code, tell me if it workes, it works with me by the
way:

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
int twos=0;
int sevens=0;
int nines=0;
int reqMoney=0;
int remainderCents=0;

cout<<"input required money"<<endl;
cin>>reqMoney;

sevens=reqMoney/7; //check how many sevens can be afforded
remainderCents= reqMoney-(sevens*7); //check the extra cents you
can use % but i prefer this i don't know why
twos= remainderCents/2; //check how many twos can be afforded for
the extra cents left
if ( (remainderCents-(twos*2)) ==1) twos++; //add one cent above
the reqmoney if the extra cents=1
if ( (sevens != 0) && (sevens<twos))
{
twos=twos-sevens;
nines=sevens;
sevens=0;
}

if ( (twos != 0) && (sevens>twos))
{
sevens=sevens-twos;
nines=twos;
twos=0;
}
cout<<"twos="<<twos<<endl;
cout<<"sevens="<<sevens<<endl;
cout<<"nines="<<nines<<endl;

system("PAUSE");
return EXIT_SUCCESS;
}

Mar 4 '07 #27

P: n/a
On Mar 4, 2:36 pm, "untitled" <awsra...@gmail.comwrote:
On Mar 4, 5:35 am, davy....@brentwood.bc.ca wrote:
On Mar 3, 9:39 pm, "untitled" <awsra...@gmail.com>
wrote:
int sevens=x/7
remainder=x - (sevens*7)
int twos= remainder/2
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
i'll write the code in few minutes.
Unless I'm much mistaken, this doesn't work. Try 81. The
correct answer is 9x9, while your algorithm would suggest
9x7, 2x9.

Here's what seems to be a general solution (the only
problem with it is that its efficiency borders on that of
bogosort):

#include <iostream>
#include <stack>
#include <map>

const int stamp_1 = 2 ;
const int stamp_2 = 7 ;
const int stamp_3 = 9 ;

namespace xyz
{ int f ( std :: map < int , int x )
{ int result = 0 ;
for
( std :: map < int , int :: iterator i =
x . begin ( ) ;
i != x . end ( ) ; ++ i )
result += ( * i ) . second ;
return result ; }
int g ( std :: map < int , int x )
{ int result = 0 ;
for
( std :: map < int , int :: iterator i =
x . begin ( ) ;
i != x . end ( ) ; ++ i )
result += ( * i ) . first * ( * i ) . second ;
return result ; }
std :: map < int , int solve
( int s , std :: stack < int c )
{ std :: map < int , int result ;
int best = 0 ;
if ( c . size ( ) )
{ result [ 0 ] = 1 ;
int cur_c = c . top ( ) ;
c . pop ( ) ;
int max_c = s / cur_c ;
std :: map < int , int tmp ;
for ( int i = 0 ; i <= max_c ; ++ i )
{ tmp = solve ( s - cur_c * i , c ) ;
if ( tmp [ 0 ] ) continue ;
tmp [ cur_c ] = i ;
if ( g ( tmp ) != s ) continue ;
int cur_val = f ( tmp ) ;
if ( ! best || cur_val < best )
{ result = tmp ; best = cur_val ; } } }
return result ; } } ;

int main ( )
{ int sum ;
std :: cin >sum ;
std :: stack < int stamps ;
stamps . push ( stamp_1 ) ;
stamps . push ( stamp_2 ) ;
stamps . push ( stamp_3 ) ;
std :: map < int , int solution =
xyz :: solve ( sum , stamps ) ;
for
( std :: map < int , int :: iterator i =
solution . begin ( ) ;
i != solution . end ( ) ; ++ i )
std :: cout << ( * i ) . first << " " <<
( * i ) . second << std :: endl ; }

--
roy axenov

Mar 4 '07 #28

P: n/a
untitled wrote:
On Mar 4, 1:36 pm, "untitled" <awsra...@gmail.comwrote:
>On Mar 4, 5:35 am, davy....@brentwood.bc.ca wrote:


On Mar 3, 9:39 pm, "untitled" <awsra...@gmail.comwrote:
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

you are right, it wasn't clear,

first i'll explain how the program will think then i'll answer your
questions:

first line will count how many 7cent stamp could be afforded with the
money required, of course there will be some extra cents we will
process it in line 2
line 2 will see how many extra cents you have after we got all the
sevens.
line 3 will check how many 2cent stamps can be afforded for that extra
cents
line 4 if the remainder was less than 2 cents (ie. 1 cent) then of
course we will consider it 2cent that is adding one cent over the
required money as you told me.
in line 5,6 we replace every 7cent and 2cent stamp to one 9cent stamp
so we got the most effective number of stamps.
line 5 if the 7c stamps was less than the 2c stamps, then combine all
the sevens with an equivilant number of 2c stamps and replace them
with 9c stamps. then delete the combined 7 and 2c stamps.
line 6 do the same if the twos was more than sevens.

the out put will be
int sevens
int nines
int twos

i'll write the code in few minutes.- Hide quoted text -

- Show quoted text -

ok here is the code, tell me if it workes, it works with me by the
way:

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
int twos=0;
int sevens=0;
int nines=0;
int reqMoney=0;
int remainderCents=0;

cout<<"input required money"<<endl;
cin>>reqMoney;

sevens=reqMoney/7; //check how many sevens can be afforded
remainderCents= reqMoney-(sevens*7); //check the extra cents you
can use % but i prefer this i don't know why
twos= remainderCents/2; //check how many twos can be afforded for
the extra cents left
if ( (remainderCents-(twos*2)) ==1) twos++; //add one cent above
the reqmoney if the extra cents=1
if ( (sevens != 0) && (sevens<twos))
{
twos=twos-sevens;
nines=sevens;
sevens=0;
}

if ( (twos != 0) && (sevens>twos))
{
sevens=sevens-twos;
nines=twos;
twos=0;
}
cout<<"twos="<<twos<<endl;
cout<<"sevens="<<sevens<<endl;
cout<<"nines="<<nines<<endl;

system("PAUSE");
return EXIT_SUCCESS;
}
I just tried it. For 100 it tells me to use

100c = 13 x 7c + 1 x 9c

This is not optimal because

100c = 4 x 7c + 8 x 9c

is better.
Best

Kai-Uwe Bux
Mar 4 '07 #29

P: n/a
This "program" is not written in c++, i'm a Java programmer , but you
will get the idea by just looking at the code.
didnt have time to comment it , the number of function can be
optimized to only one if you forward where you want the function to
start as a second varible :)

Hope it works for you .


//three function are used to calculate the lest number of stamps
needed

function int dvide_9 (int money)
{
int num = 0;
rest = moeny%9
num=num+(moeny/9)
if (rest = 8) {

num=num+1
rest = 0;
}
rest = rest%7
num = num +(rest/7)
if (rest = 6) {

num=num+1
rest = 0;
}
rest = rest % 2
num = num + (rest/2)
if (rest = 1) {

num=num+1
rest = 0;
}

resturn num;
}
function int dvide_7 (int money)
{
int num = 0;

rest = money%7
num = num +(money/7)
if (rest = 6) {

num=num+1
rest = 0;
}
rest = rest % 2
num = num + (rest/2)
if (rest = 1) {

num=num+1
rest = 0;
}

resturn num;
}

function int dvide_2 (int money)
{
int num = 0;

rest = money % 2
num = num + (money/2)
if (rest = 1) {

num=num+1
rest = 0;
}

resturn num;
}

--------------------------------------------------
main program

choses the function with less number of (num value) which is the
number of stamps used.

Mar 4 '07 #30

P: n/a
<da******@brentwood.bc.cawrote in message
news:11**********************@30g2000cwc.googlegro ups.com...
>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.
[...]

Here is exactly how to get the job done!
#define STAMP_BASE_PRICE() 4
#define STAMP_DEPTH() 7
#define BUYOFFERS_DEPTH() 12

#define STAMP_STATICINIT() \
{STAMP_BASE_PRICE(), 7, 9, 12, 19, 25, 50}

#define BUYOFFERS_STATICINIT() \
{48, 11, 1, 74, 3, 8, 14, 23, 33, 13, 123, 87}
int main() {
int i;
int const stamps[STAMP_DEPTH()] = STAMP_STATICINIT();
int const buyoffers[BUYOFFERS_DEPTH()] = BUYOFFERS_STATICINIT();

for(i = 0; i < BUYOFFERS_DEPTH(); ++i) {
int x, p;
int base = buyoffers[i];
int remainder = base;

printf("-- press <ENTERto execute transaction (%d) --\n", i);
getchar();
printf("(%d)transaction::executing for (%d) cents\n", i, base);
printf("__________________________________________ ______________________\n");

while(remainder >= STAMP_BASE_PRICE()) {
for(x = STAMP_DEPTH() - 1; x -1; --x) {
p = stamps[x];
printf("\n checking stamp price of (%d) against remainder (%d)\n",
p, remainder);
while (remainder >= p) {
remainder -= p;
printf(" sold a (%d) cent stamp! remainder (%d)\n", p,
remainder);
}
}
}

printf("\n(%d)transaction::commited with (%d) cents change\n", i,
remainder);
printf("__________________________________________ ______________________\n\n\n\n");
}

return 0;
}

Any thoughts? :^)
Mar 4 '07 #31

P: n/a
"Chris Thomasson" <cr*****@comcast.netwrote in message
news:qc******************************@comcast.com. ..
<da******@brentwood.bc.cawrote in message
news:11**********************@30g2000cwc.googlegro ups.com...
>>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.
[...]

Here is exactly how to get the job done!
here is another way... A much better way indeed:
#define STAMP_BASE_PRICE() 4
#define STAMP_DEPTH() 7
#define BUYOFFERS_DEPTH() 12

#define STAMP_STATICINIT() \
{STAMP_BASE_PRICE(), 7, 12, 15, 18, 25, 32}

#define BUYOFFERS_STATICINIT() \
{248, 211, 1, 274, 122, 143, 214, 176, 87, 213, 323, 587}
int main() {
int i;
int const stamps[STAMP_DEPTH()] = STAMP_STATICINIT();
int const buyoffers[BUYOFFERS_DEPTH()] = BUYOFFERS_STATICINIT();

for(i = 0; i < BUYOFFERS_DEPTH(); ++i) {
int x, p, r;
int base = buyoffers[i];
int remainder = base;

printf("-- press <ENTERto execute transaction (%d) --\n", i);
getchar();
printf("(%d)transaction::executing for (%d) cents\n", i, base);
printf("__________________________________________ ______________________\n");

while(remainder >= STAMP_BASE_PRICE()) {
for(x = STAMP_DEPTH() - 1; x -1; --x) {
p = stamps[x];
printf("\n checking stamp price of (%d) against remainder (%d)\n",
p, remainder);
if (remainder >= p) {
r = remainder / p;
remainder -= r * p;
printf(" sold (%d) stamp(s) worth (%d) cents each! remainder
(%d)\n", r, p, remainder);
}
}
}

printf("\n(%d)transaction::committed with (%d) cents change\n", i,
remainder);
printf("__________________________________________ ______________________\n\n\n\n");
}

return 0;
}
can you notice the subtle change in the algorithm? Man, that works faster
that the other one I posted!
:O
Mar 4 '07 #32

P: n/a
I know what's missing...

#include <cstdio>
printf tend to get crabby when its used and there is nobody around to
declare it!
Mar 4 '07 #33

P: n/a

"Kai-Uwe Bux" <jk********@gmx.netwrote in message
news:es**********@murdoch.acc.Virginia.EDU...
osmium wrote:
><da******@brentwood.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?
That requires "backtracking". If a partial solution yields a remainder of
one cent, then you need to try reducing the previous chosen count by 1, and
trying again.

So for 10, you'd try 10/9 = 1 remainder 1. 1 cannot be generated with any
of 2, 7, or 9, so try 1 less 9-center, which would be zero 9-centers. Next
comes 7-centers, so try 10/7 = 1 rem.3. Then, 3/2 = 1 rem1, and again it
canot be solved from here, so backtrack again, with one less 7-center,
(which is zero), leaving only 2-centers available. 10/2 = 5 rem.0, so it's
solved as 0 9-centers, 0 7-centers, and 5 2-centers.

For 35, 35/9 = 3 rem.8. Then, 8/7 = 1 rem1, which is illegal, so youre left
with 2-centers as before, with 8/2 = 4 rem.0. So you get 3 9-centers, 0
7-centers and 4 2-centers.

BTW, it's easy to see that the problem is not solvable at all for starting
values of 1, 3, or 5 cents.

-Howard
Mar 4 '07 #34

P: n/a
Howard wrote:
>
"Kai-Uwe Bux" <jk********@gmx.netwrote in message
news:es**********@murdoch.acc.Virginia.EDU...
>osmium wrote:
>><da******@brentwood.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?

That requires "backtracking". If a partial solution yields a remainder of
one cent, then you need to try reducing the previous chosen count by 1,
and trying again.

So for 10, you'd try 10/9 = 1 remainder 1. 1 cannot be generated with any
of 2, 7, or 9, so try 1 less 9-center, which would be zero 9-centers.
Next
comes 7-centers, so try 10/7 = 1 rem.3. Then, 3/2 = 1 rem1, and again it
canot be solved from here, so backtrack again, with one less 7-center,
(which is zero), leaving only 2-centers available. 10/2 = 5 rem.0, so
it's solved as 0 9-centers, 0 7-centers, and 5 2-centers.

For 35, 35/9 = 3 rem.8. Then, 8/7 = 1 rem1, which is illegal, so youre
left
with 2-centers as before, with 8/2 = 4 rem.0. So you get 3 9-centers, 0
7-centers and 4 2-centers.
Yes,

35c = 3 x 9c + 4 x 2c (total of 7 stamps)

is what this backtracking gets you. But it is not the correct answer, which
is:

35c = 5 x 7c (total of 5 stamps)

BTW, it's easy to see that the problem is not solvable at all for starting
values of 1, 3, or 5 cents.
Correct.
Best

Kai-Uwe Bux
Mar 4 '07 #35

P: n/a
roy axenov wrote:
On Mar 4, 2:36 pm, "untitled" <awsra...@gmail.comwrote:
>On Mar 4, 5:35 am, davy....@brentwood.bc.ca wrote:
On Mar 3, 9:39 pm, "untitled" <awsra...@gmail.com>
wrote:
int sevens=x/7
remainder=x - (sevens*7)
int twos= remainder/2
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
i'll write the code in few minutes.

Unless I'm much mistaken, this doesn't work. Try 81. The
correct answer is 9x9, while your algorithm would suggest
9x7, 2x9.

Here's what seems to be a general solution (the only
problem with it is that its efficiency borders on that of
bogosort):

#include <iostream>
#include <stack>
#include <map>

const int stamp_1 = 2 ;
const int stamp_2 = 7 ;
const int stamp_3 = 9 ;

namespace xyz
{ int f ( std :: map < int , int x )
{ int result = 0 ;
for
( std :: map < int , int :: iterator i =
x . begin ( ) ;
i != x . end ( ) ; ++ i )
result += ( * i ) . second ;
return result ; }
int g ( std :: map < int , int x )
{ int result = 0 ;
for
( std :: map < int , int :: iterator i =
x . begin ( ) ;
i != x . end ( ) ; ++ i )
result += ( * i ) . first * ( * i ) . second ;
return result ; }
std :: map < int , int solve
( int s , std :: stack < int c )
{ std :: map < int , int result ;
int best = 0 ;
if ( c . size ( ) )
{ result [ 0 ] = 1 ;
int cur_c = c . top ( ) ;
c . pop ( ) ;
int max_c = s / cur_c ;
std :: map < int , int tmp ;
for ( int i = 0 ; i <= max_c ; ++ i )
{ tmp = solve ( s - cur_c * i , c ) ;
if ( tmp [ 0 ] ) continue ;
tmp [ cur_c ] = i ;
if ( g ( tmp ) != s ) continue ;
int cur_val = f ( tmp ) ;
if ( ! best || cur_val < best )
{ result = tmp ; best = cur_val ; } } }
return result ; } } ;

int main ( )
{ int sum ;
std :: cin >sum ;
std :: stack < int stamps ;
stamps . push ( stamp_1 ) ;
stamps . push ( stamp_2 ) ;
stamps . push ( stamp_3 ) ;
std :: map < int , int solution =
xyz :: solve ( sum , stamps ) ;
for
( std :: map < int , int :: iterator i =
solution . begin ( ) ;
i != solution . end ( ) ; ++ i )
std :: cout << ( * i ) . first << " " <<
( * i ) . second << std :: endl ; }
Nice, the first correct solution I have seen in this thread. But it really
gets a little slow on larger numbers. Also, it does not give all solutions.
Try producing this output:
news_grouptime a.out 10000 10040
10000 = 1108 x 9c + 4 x 7c + 0 x 2c
10001 = 1111 x 9c + 0 x 7c + 1 x 2c
10002 = 1109 x 9c + 3 x 7c + 0 x 2c
10003 = 1106 x 9c + 7 x 7c + 0 x 2c = 1111 x 9c + 0 x 7c + 2 x 2c
10004 = 1110 x 9c + 2 x 7c + 0 x 2c
10005 = 1107 x 9c + 6 x 7c + 0 x 2c
10006 = 1111 x 9c + 1 x 7c + 0 x 2c
10007 = 1108 x 9c + 5 x 7c + 0 x 2c
10008 = 1112 x 9c + 0 x 7c + 0 x 2c
10009 = 1109 x 9c + 4 x 7c + 0 x 2c
10010 = 1112 x 9c + 0 x 7c + 1 x 2c
10011 = 1110 x 9c + 3 x 7c + 0 x 2c
10012 = 1107 x 9c + 7 x 7c + 0 x 2c = 1112 x 9c + 0 x 7c + 2 x 2c
10013 = 1111 x 9c + 2 x 7c + 0 x 2c
10014 = 1108 x 9c + 6 x 7c + 0 x 2c
10015 = 1112 x 9c + 1 x 7c + 0 x 2c
10016 = 1109 x 9c + 5 x 7c + 0 x 2c
10017 = 1113 x 9c + 0 x 7c + 0 x 2c
10018 = 1110 x 9c + 4 x 7c + 0 x 2c
10019 = 1113 x 9c + 0 x 7c + 1 x 2c
10020 = 1111 x 9c + 3 x 7c + 0 x 2c
10021 = 1108 x 9c + 7 x 7c + 0 x 2c = 1113 x 9c + 0 x 7c + 2 x 2c
10022 = 1112 x 9c + 2 x 7c + 0 x 2c
10023 = 1109 x 9c + 6 x 7c + 0 x 2c
10024 = 1113 x 9c + 1 x 7c + 0 x 2c
10025 = 1110 x 9c + 5 x 7c + 0 x 2c
10026 = 1114 x 9c + 0 x 7c + 0 x 2c
10027 = 1111 x 9c + 4 x 7c + 0 x 2c
10028 = 1114 x 9c + 0 x 7c + 1 x 2c
10029 = 1112 x 9c + 3 x 7c + 0 x 2c
10030 = 1109 x 9c + 7 x 7c + 0 x 2c = 1114 x 9c + 0 x 7c + 2 x 2c
10031 = 1113 x 9c + 2 x 7c + 0 x 2c
10032 = 1110 x 9c + 6 x 7c + 0 x 2c
10033 = 1114 x 9c + 1 x 7c + 0 x 2c
10034 = 1111 x 9c + 5 x 7c + 0 x 2c
10035 = 1115 x 9c + 0 x 7c + 0 x 2c
10036 = 1112 x 9c + 4 x 7c + 0 x 2c
10037 = 1115 x 9c + 0 x 7c + 1 x 2c
10038 = 1113 x 9c + 3 x 7c + 0 x 2c
10039 = 1110 x 9c + 7 x 7c + 0 x 2c = 1115 x 9c + 0 x 7c + 2 x 2c

real 0m0.011s
user 0m0.008s
sys 0m0.004s
Best

Kai-Uwe Bux
Mar 5 '07 #36

P: n/a
[...]
Nice, the first correct solution I have seen in this thread.
What about the one I posted here:

http://groups.google.com/group/comp....9519253ff80cdf

?
Mar 5 '07 #37

P: n/a
Chris Thomasson wrote:
What about the one I posted here:

http://groups.google.com/group/comp....9519253ff80cdf
After changing the constants so that they actually match the problem of the
OP:
#define STAMP_BASE_PRICE() 2
#define STAMP_DEPTH() 3
#define BUYOFFERS_DEPTH() 2

#define STAMP_STATICINIT() \
{STAMP_BASE_PRICE(), 7, 9 }

#define BUYOFFERS_STATICINIT() \
{35, 100}
I get:

(0)transaction::executing for (35) cents
__________________________________________________ ______________

checking stamp price of (9) against remainder (35)
sold (3) stamp(s) worth (9) cents each! remainder (8)

checking stamp price of (7) against remainder (8)
sold (1) stamp(s) worth (7) cents each! remainder (1)

checking stamp price of (2) against remainder (1)

(0)transaction::committed with (1) cents change
__________________________________________________ ______________
That is, your program tells me:

35c = 3 x 9c + 1 x 7c + 0 x 2c + change

which, I think, is not what the OP's assignment asked for. I would gather
that

35c = 0 x 9c + 5 x 7c + 0 x 2c

is the right solution. If you put the stamps you bought on the envelope, the
postal service will frown upon it: you are shy 1c of the required postage.
Best

Kai-Uwe Bux
Mar 5 '07 #38

P: n/a
That is, your program tells me:
>
35c = 3 x 9c + 1 x 7c + 0 x 2c + change

which, I think, is not what the OP's assignment asked for. I would gather
that

35c = 0 x 9c + 5 x 7c + 0 x 2c

is the right solution. If you put the stamps you bought on the envelope,
the
postal service will frown upon it: you are shy 1c of the required postage.
Okay. So then change my programs main while loop to the following and we
have lift off!

________

#define STAMP_BASE_PRICE() 2
#define STAMP_DEPTH() 3
#define BUYOFFERS_DEPTH() 2

#define STAMP_STATICINIT() \
{STAMP_BASE_PRICE(), 7, 9 }

#define BUYOFFERS_STATICINIT() \
{35, 100}
int main() {
int i;
int const stamps[STAMP_DEPTH()] = STAMP_STATICINIT();
int const buyoffers[BUYOFFERS_DEPTH()] = BUYOFFERS_STATICINIT();

for(i = 0; i < BUYOFFERS_DEPTH(); ++i) {
int x, p, r;
int base = buyoffers[i];
int remainder = base;

printf("-- press <ENTERto execute transaction (%d) --\n", i);
getchar();
printf("(%d)transaction::executing for (%d) cents\n", i, base);
printf("__________________________________________ ______________________\n");

while(remainder >= STAMP_BASE_PRICE()) {

// check for the perfect match
for(x = STAMP_DEPTH() - 1; x -1; --x) {
p = stamps[x];
printf("\n checking stamp price of (%d) against remainder (%d)\n",
p, remainder);
if (remainder >= p && ! (remainder % p)) {
r = remainder / p;
remainder -= r * p;
printf(" sold (%d) stamp(s) worth (%d) cents each! remainder
(%d)\n", r, p, remainder);
break;
}
}

// check for any match!
for(x = STAMP_DEPTH() - 1; x -1; --x) {
p = stamps[x];
printf("\n checking stamp price of (%d) against remainder (%d)\n",
p, remainder);
if (remainder >= p) {
r = remainder / p;
remainder -= r * p;
printf(" sold (%d) stamp(s) worth (%d) cents each! remainder
(%d)\n", r, p, remainder);
}
}
}

printf("\n(%d)transaction::commited with (%d) cents change\n", i,
remainder);
printf("__________________________________________ ______________________\n\n\n\n");
}

return 0;
}


This algorithm should completely solve the OP's problem; any thoughts?
Mar 5 '07 #39

P: n/a
Chris Thomasson wrote:
>That is, your program tells me:

35c = 3 x 9c + 1 x 7c + 0 x 2c + change

which, I think, is not what the OP's assignment asked for. I would gather
that

35c = 0 x 9c + 5 x 7c + 0 x 2c

is the right solution. If you put the stamps you bought on the envelope,
the
postal service will frown upon it: you are shy 1c of the required
postage.

Okay. So then change my programs main while loop to the following and we
have lift off!

________

#define STAMP_BASE_PRICE() 2
#define STAMP_DEPTH() 3
#define BUYOFFERS_DEPTH() 2

#define STAMP_STATICINIT() \
{STAMP_BASE_PRICE(), 7, 9 }

#define BUYOFFERS_STATICINIT() \
{35, 100}
int main() {
int i;
int const stamps[STAMP_DEPTH()] = STAMP_STATICINIT();
int const buyoffers[BUYOFFERS_DEPTH()] = BUYOFFERS_STATICINIT();

for(i = 0; i < BUYOFFERS_DEPTH(); ++i) {
int x, p, r;
int base = buyoffers[i];
int remainder = base;

printf("-- press <ENTERto execute transaction (%d) --\n", i);
getchar();
printf("(%d)transaction::executing for (%d) cents\n", i, base);
printf("__________________________________________ ______________________\n");
>
while(remainder >= STAMP_BASE_PRICE()) {

// check for the perfect match
for(x = STAMP_DEPTH() - 1; x -1; --x) {
p = stamps[x];
printf("\n checking stamp price of (%d) against remainder
(%d)\n",
p, remainder);
if (remainder >= p && ! (remainder % p)) {
r = remainder / p;
remainder -= r * p;
printf(" sold (%d) stamp(s) worth (%d) cents each! remainder
(%d)\n", r, p, remainder);
break;
}
}

// check for any match!
for(x = STAMP_DEPTH() - 1; x -1; --x) {
p = stamps[x];
printf("\n checking stamp price of (%d) against remainder
(%d)\n",
p, remainder);
if (remainder >= p) {
r = remainder / p;
remainder -= r * p;
printf(" sold (%d) stamp(s) worth (%d) cents each! remainder
(%d)\n", r, p, remainder);
}
}
}

printf("\n(%d)transaction::commited with (%d) cents change\n", i,
remainder);
printf("__________________________________________ ______________________\n\n\n\n");
}

return 0;
}


This algorithm should completely solve the OP's problem; any thoughts?

As far as I understand the OP's problem, it asks for a way to realize a
given postage exactly with the minimum number of stamps. Your program still
does not do it. It says:
news_groupa.out
-- press <ENTERto execute transaction (0) --

(0)transaction::executing for (35) cents
__________________________________________________ ______________

checking stamp price of (9) against remainder (35)

checking stamp price of (7) against remainder (35)
sold (5) stamp(s) worth (7) cents each! remainder (0)

checking stamp price of (9) against remainder (0)

checking stamp price of (7) against remainder (0)

checking stamp price of (2) against remainder (0)

(0)transaction::commited with (0) cents change
__________________________________________________ ______________

-- press <ENTERto execute transaction (1) --

(1)transaction::executing for (100) cents
__________________________________________________ ______________

checking stamp price of (9) against remainder (100)

checking stamp price of (7) against remainder (100)

checking stamp price of (2) against remainder (100)
sold (50) stamp(s) worth (2) cents each! remainder (0)

checking stamp price of (9) against remainder (0)

checking stamp price of (7) against remainder (0)

checking stamp price of (2) against remainder (0)

(1)transaction::commited with (0) cents change
__________________________________________________ ______________

In other words, it wants

100c = 50 x 2c (50 stamps used)

instead of

100c = 8 x 9c + 4 x 7c (12 stamps used)

Best

Kai-Uwe Bux
Mar 5 '07 #40

P: n/a
On Mar 5, 3:54 am, Kai-Uwe Bux <jkherci...@gmx.netwrote:
roy axenov wrote:
[2-, 7- and 9-cent stamps]
Here's what seems to be a general solution (the only
problem with it is that its efficiency borders on that
of bogosort):
[code]
Nice, the first correct solution I have seen in this
thread. But it really gets a little slow on larger
numbers.
Well, using the ideas mentioned earlier in the thread it is
relatively easy to achieve a significant improvement in
performance, at least for the 2-7-9 case. There's still a
noticeable decrease in performance for 3-13-14-15 case, and
something like 3-5-112-1113-10001 would be outright scary.

I wonder if the period is always equal to the largest
coefficient for suffiently large n? It seems so even though
it's kinda counter-intuitive.
Also, it does not give all solutions.
Actually, the code posted seems to find all the
solutions... It just doesn't bother remembering them all.
Try producing this output:
[sample output]

#include <iostream>
#include <vector>
#include <map>

const int stamp_1 = 2 ;
const int stamp_2 = 7 ;
const int stamp_3 = 9 ;

namespace xyz
{
class dio
{
public :
dio ( const std :: vector < int & c ) ;

std :: vector < std :: map < int , int solve
( int s ) const
{ return slv ( s , m_ . begin ( ) ) ; }

private :
std :: map < int , int m_ ;

std :: vector < std :: map < int , int slv
(
int s ,
std :: map < int , int :: const_iterator im
) const ;

static int trl
(
const std :: map < int , int & x ,
int ( * f ) ( const std :: pair < int , int & )
) ;

static int eff
( const std :: pair < int , int & x )
{ return x . second ; }
static int ttl
( const std :: pair < int , int & x )
{ return x . first * x . second ; }
} ;

dio :: dio ( const std :: vector < int & c )
{
for
(
std :: vector < int :: const_iterator ic =
c . begin ( ) ;
ic != c . end ( ) ; ++ ic
)
{
m_ [ * ic ] = 0 ;
for
(
std :: vector < int :: const_iterator jc =
ic + 1 ;
jc != c . end ( ) ; ++ jc
)
if ( * jc m_ [ * ic ] ) m_ [ * ic ] = * jc ;
}
}

int dio :: trl
(
const std :: map < int , int & x ,
int ( * f ) ( const std :: pair < int , int & )
)
{
int result = 0 ;
for
(
std :: map < int , int :: const_iterator i =
x . begin ( ) ;
i != x . end ( ) ; ++ i
)
result += ( * f ) ( * i ) ;
return result ;
}

std :: vector < std :: map < int , int dio :: slv
(
int s ,
std :: map < int , int :: const_iterator im
) const
{
std :: vector < std :: map < int , int result ;
int best = 0 ;

if ( im != m_ . end ( ) )
{
std :: map < int , int empty ;
empty [ 0 ] = 1 ;
result . push_back ( empty ) ;

int cur_c = ( * im ) . first ;
int div_c = s / cur_c ;
int max_c =
std :: min ( ( * im ) . second , div_c ) ;

std :: map < int , int tmp ;

++ im ;

if ( max_c )
{
for ( int i = 0 ; i <= max_c ; ++ i )
{
std :: vector < std :: map < int , int sols =
slv ( s - cur_c * i , im ) ;

for
(
std :: vector < std :: map < int , int
:: const_iterator is = sols . begin ( ) ;
is != sols . end ( ) ; ++ is
)
{
tmp = * is ;
if ( tmp [ 0 ] ) continue ;

tmp [ cur_c ] = i ;
if ( trl ( tmp , & ttl ) != s ) continue ;

int cur_val = trl ( tmp , & eff ) ;
if ( ! best || cur_val < best )
{
result . clear ( ) ;
best = cur_val ;
}
if ( cur_val == best )
result . push_back ( tmp ) ;
}
}
}
else
{
tmp [ cur_c ] = div_c ;
if ( trl ( tmp , & dio :: ttl ) == s )
{
result . clear ( ) ;
result . push_back ( tmp ) ;
}
}
}
return result ;
}
} ;

int main ( int argc , char * argv [ ] )
{
std :: vector < int stamps ;
stamps . push_back ( stamp_1 ) ;
stamps . push_back ( stamp_2 ) ;
stamps . push_back ( stamp_3 ) ;

xyz :: dio d ( stamps ) ;

int max_sum = atoi ( argv [ 2 ] ) ;
for
(
int sum = atoi ( argv [ 1 ] ) ;
sum <= max_sum ; ++ sum
)
{
std :: vector < std :: map < int , int solutions =
d . solve ( sum ) ;

std :: cout << sum << " " ;
for
(
std :: vector < std :: map < int , int ::
const_iterator si = solutions . begin ( ) ;
si != solutions . end ( ) ; ++ si
)
{
std :: cout << "= " ;
for
(
std :: map < int , int :: const_iterator i =
( * si ) . begin ( ) ;
i != ( * si ) . end ( ) ; ++ i
)
if ( ( * i ) . first )
std :: cout << ( * i ) . second << " x " <<
( * i ) . first << "c " ;
}
std :: cout << std :: endl ;
}
}

pavel@debian:~/dev/cxx/t14$ time ./a.out 10000 10040
10000 = 0 x 2c 4 x 7c 1108 x 9c
10001 = 1 x 2c 0 x 7c 1111 x 9c
10002 = 0 x 2c 3 x 7c 1109 x 9c
10003 = 0 x 2c 7 x 7c 1106 x 9c = 2 x 2c 0 x 7c 1111 x 9c
10004 = 0 x 2c 2 x 7c 1110 x 9c
10005 = 0 x 2c 6 x 7c 1107 x 9c
10006 = 0 x 2c 1 x 7c 1111 x 9c
10007 = 0 x 2c 5 x 7c 1108 x 9c
10008 = 0 x 2c 0 x 7c 1112 x 9c
10009 = 0 x 2c 4 x 7c 1109 x 9c
10010 = 1 x 2c 0 x 7c 1112 x 9c
10011 = 0 x 2c 3 x 7c 1110 x 9c
10012 = 0 x 2c 7 x 7c 1107 x 9c = 2 x 2c 0 x 7c 1112 x 9c
10013 = 0 x 2c 2 x 7c 1111 x 9c
10014 = 0 x 2c 6 x 7c 1108 x 9c
10015 = 0 x 2c 1 x 7c 1112 x 9c
10016 = 0 x 2c 5 x 7c 1109 x 9c
10017 = 0 x 2c 0 x 7c 1113 x 9c
10018 = 0 x 2c 4 x 7c 1110 x 9c
10019 = 1 x 2c 0 x 7c 1113 x 9c
10020 = 0 x 2c 3 x 7c 1111 x 9c
10021 = 0 x 2c 7 x 7c 1108 x 9c = 2 x 2c 0 x 7c 1113 x 9c
10022 = 0 x 2c 2 x 7c 1112 x 9c
10023 = 0 x 2c 6 x 7c 1109 x 9c
10024 = 0 x 2c 1 x 7c 1113 x 9c
10025 = 0 x 2c 5 x 7c 1110 x 9c
10026 = 0 x 2c 0 x 7c 1114 x 9c
10027 = 0 x 2c 4 x 7c 1111 x 9c
10028 = 1 x 2c 0 x 7c 1114 x 9c
10029 = 0 x 2c 3 x 7c 1112 x 9c
10030 = 0 x 2c 7 x 7c 1109 x 9c = 2 x 2c 0 x 7c 1114 x 9c
10031 = 0 x 2c 2 x 7c 1113 x 9c
10032 = 0 x 2c 6 x 7c 1110 x 9c
10033 = 0 x 2c 1 x 7c 1114 x 9c
10034 = 0 x 2c 5 x 7c 1111 x 9c
10035 = 0 x 2c 0 x 7c 1115 x 9c
10036 = 0 x 2c 4 x 7c 1112 x 9c
10037 = 1 x 2c 0 x 7c 1115 x 9c
10038 = 0 x 2c 3 x 7c 1113 x 9c
10039 = 0 x 2c 7 x 7c 1110 x 9c = 2 x 2c 0 x 7c 1115 x 9c
10040 = 0 x 2c 2 x 7c 1114 x 9c

real 0m0.008s
user 0m0.004s
sys 0m0.000s

--
Pavel Lepin

Mar 5 '07 #41

P: n/a
>
35c = 3 x 9c + 4 x 2c (total of 7 stamps)

is what this backtracking gets you. But it is not the correct answer,
which
is:

35c = 5 x 7c (total of 5 stamps)

Oops! :-} Guess my memories from school are fading slowly away...

-H
Mar 5 '07 #42

P: n/a
"Kai-Uwe Bux" <jk********@gmx.netwrote in message
news:es**********@murdoch.acc.Virginia.EDU...
Chris Thomasson wrote:
>>That is, your program tells me:

35c = 3 x 9c + 1 x 7c + 0 x 2c + change

which, I think, is not what the OP's assignment asked for. I would
gather
that
I would gather that I only have two feet to put in my mouth (e.g., the two
examples that do not address the requirements!)... I guess I deserve it when
I don't spend more time than 2-4 minutes of reading the OP's post and typing
in a newsreader console to create a solution!

:^0

Sorry for that non-sense!
Mar 6 '07 #43

P: n/a
p.*****@ctncorp.com wrote:
On Mar 5, 3:54 am, Kai-Uwe Bux <jkherci...@gmx.netwrote:
>roy axenov wrote:

[2-, 7- and 9-cent stamps]
Here's what seems to be a general solution (the only
problem with it is that its efficiency borders on that
of bogosort):

[code]
>Nice, the first correct solution I have seen in this
thread. But it really gets a little slow on larger
numbers.

Well, using the ideas mentioned earlier in the thread it is
relatively easy to achieve a significant improvement in
performance, at least for the 2-7-9 case. There's still a
noticeable decrease in performance for 3-13-14-15 case, and
something like 3-5-112-1113-10001 would be outright scary.

I wonder if the period is always equal to the largest
coefficient for suffiently large n? It seems so even though
it's kinda counter-intuitive.
I think it is intuitively clear: Let a_max be the highest stamp value. For
sufficiently large n, you will definitely use some stamps of value a_max in
an optimal configuration for n. In that case, however, you must obtain an
optimal configuration for the amount n-a_max by leaving out one of the
a_max stamps (if you could do better than that for n-a_max, you could
obtain a better configuration for n by adding in a stamp of value a_max).
This shows how an optimal solution for n and a solution for n-a_max are
related. This is where the periodicity lies.

>Also, it does not give all solutions.

Actually, the code posted seems to find all the
solutions... It just doesn't bother remembering them all.
>Try producing this output:

[sample output]
[code snipped]
pavel@debian:~/dev/cxx/t14$ time ./a.out 10000 10040
10000 = 0 x 2c 4 x 7c 1108 x 9c
10001 = 1 x 2c 0 x 7c 1111 x 9c
10002 = 0 x 2c 3 x 7c 1109 x 9c
10003 = 0 x 2c 7 x 7c 1106 x 9c = 2 x 2c 0 x 7c 1111 x 9c
10004 = 0 x 2c 2 x 7c 1110 x 9c
10005 = 0 x 2c 6 x 7c 1107 x 9c
10006 = 0 x 2c 1 x 7c 1111 x 9c
10007 = 0 x 2c 5 x 7c 1108 x 9c
10008 = 0 x 2c 0 x 7c 1112 x 9c
10009 = 0 x 2c 4 x 7c 1109 x 9c
10010 = 1 x 2c 0 x 7c 1112 x 9c
10011 = 0 x 2c 3 x 7c 1110 x 9c
10012 = 0 x 2c 7 x 7c 1107 x 9c = 2 x 2c 0 x 7c 1112 x 9c
10013 = 0 x 2c 2 x 7c 1111 x 9c
10014 = 0 x 2c 6 x 7c 1108 x 9c
10015 = 0 x 2c 1 x 7c 1112 x 9c
10016 = 0 x 2c 5 x 7c 1109 x 9c
10017 = 0 x 2c 0 x 7c 1113 x 9c
10018 = 0 x 2c 4 x 7c 1110 x 9c
10019 = 1 x 2c 0 x 7c 1113 x 9c
10020 = 0 x 2c 3 x 7c 1111 x 9c
10021 = 0 x 2c 7 x 7c 1108 x 9c = 2 x 2c 0 x 7c 1113 x 9c
10022 = 0 x 2c 2 x 7c 1112 x 9c
10023 = 0 x 2c 6 x 7c 1109 x 9c
10024 = 0 x 2c 1 x 7c 1113 x 9c
10025 = 0 x 2c 5 x 7c 1110 x 9c
10026 = 0 x 2c 0 x 7c 1114 x 9c
10027 = 0 x 2c 4 x 7c 1111 x 9c
10028 = 1 x 2c 0 x 7c 1114 x 9c
10029 = 0 x 2c 3 x 7c 1112 x 9c
10030 = 0 x 2c 7 x 7c 1109 x 9c = 2 x 2c 0 x 7c 1114 x 9c
10031 = 0 x 2c 2 x 7c 1113 x 9c
10032 = 0 x 2c 6 x 7c 1110 x 9c
10033 = 0 x 2c 1 x 7c 1114 x 9c
10034 = 0 x 2c 5 x 7c 1111 x 9c
10035 = 0 x 2c 0 x 7c 1115 x 9c
10036 = 0 x 2c 4 x 7c 1112 x 9c
10037 = 1 x 2c 0 x 7c 1115 x 9c
10038 = 0 x 2c 3 x 7c 1113 x 9c
10039 = 0 x 2c 7 x 7c 1110 x 9c = 2 x 2c 0 x 7c 1115 x 9c
10040 = 0 x 2c 2 x 7c 1114 x 9c

real 0m0.008s
user 0m0.004s
sys 0m0.000s
Very, very nice. The most impressive part is that the code is so contrived
and thouroughly obfuscated that I still have a hard time understanding how
it works. This is a fine example for how one can post a solution to a
homework problem that the OP could not reasonably use.
Best

Kai-Uwe Bux
Mar 6 '07 #44

P: n/a
On Mar 6, 5:20 am, Kai-Uwe Bux <jkherci...@gmx.netwrote:
p.le...@ctncorp.com wrote:
[2-, 7- and 9-cent stamps]
I wonder if the period is always equal to the largest
coefficient for suffiently large n? It seems so even
though it's kinda counter-intuitive.

I think it is intuitively clear:
[proof]

In my defense, while my C++ is a bit rusty, my math
intuition seems to have actually fossilized from disuse.

[sample output]
Very, very nice.
There are a couple of subtle bugs in the code, by the way.
The most impressive part is that the code is so contrived
and thouroughly obfuscated that I still have a hard time
understanding how it works.
I freely admit that the slv() member function is an awful
mess. In my defense, the public interface is fairly clear,
and the terrible things going on in the deep, dark bowels
of a component are of no concern to the user of said
component. Also, if this was production-grade code, I
would've spent some time polishing and annotating it, so it
wouldn't have been *that* bad.

Anyway, while the solution given above does work for the
OP's problem, I decided to see if it could be improved on.
As I said, my math intuition is in no good shape, so I'm
not certain I got the period detection right. Here goes
nothing:

#include <cassert>
#include <string>
#include <iostream>
#include <istream>
#include <ostream>
#include <sstream>
#include <vector>
#include <map>

namespace xyz
{
class dio
{
public :

typedef unsigned long coeff ;

typedef std :: vector < coeff coeff_vec ;
typedef std :: map < coeff , coeff coeff_map ;
typedef std :: vector < coeff_map sol_vec ;

typedef coeff_vec :: const_iterator coeff_vec_citr ;
typedef coeff_map :: const_iterator coeff_map_citr ;
typedef sol_vec :: const_iterator sol_vec_citr ;

class sol
{
public :

bool is_sol ( ) const { return is_sol_ ; }
coeff eff ( ) const { return eff_ ; }

const sol_vec & s_ref ( ) const { return s_ ; }

protected :

friend class dio ;

sol ( ) : is_sol_ ( false ) , eff_ ( 0 ) { }
sol ( coeff c ) ;
sol ( const sol & s , coeff c , coeff i = 1 ) ;

bool has ( coeff c ) const ;
bool has ( const coeff_map & sol ) const ;

void add ( const sol & s ) ;

bool operator == ( const sol & s ) const
{
return
( is_sol ( ) == s . is_sol ( ) ) &&
( eff ( ) == s . eff ( ) ) ;
}
bool operator ( const sol & s ) const
{
return
( ! is_sol ( ) && s . is_sol ( ) ) ||
(
( is_sol ( ) && s . is_sol ( ) ) &&
( eff ( ) s . eff ( ) )
) ;
}
bool operator < ( const sol & s ) const
{ return s * this ; }
bool operator >= ( const sol & s ) const
{ return ( * this s ) || ( * this == s ) ; }
bool operator <= ( const sol & s ) const
{ return ( * this < s ) || ( * this == s ) ; }

private :

bool is_sol_ ;
coeff eff_ ;
sol_vec s_ ;
} ;

dio ( const coeff_vec & c ) ;

void init ( ) ;

sol solve ( coeff sum ) ;

private :

typedef std :: vector < sol sols_vec ;

typedef sols_vec :: const_iterator sols_vec_citr ;

bool inited_ ;

coeff max_coeff_ ;
coeff_map coeffs_ ;

sols_vec precomp_ ;

void populate ( ) ;

bool pop_c ( coeff c ) ;
bool pop ( coeff c ) ;
} ;

dio :: dio ( const coeff_vec & c ) : inited_ ( false )
{
for
(
coeff_vec_citr i_coeff = c . begin ( ) ;
i_coeff != c . end ( ) ; ++ i_coeff
)
{
assert ( 0 < * i_coeff ) ;
assert ( ! coeffs_ [ * i_coeff ] ) ;

coeffs_ [ * i_coeff ] = 1 ;
}

max_coeff_ = ( * ( -- coeffs_ . end ( ) ) ) . first ;
}

void dio :: init ( )
{
assert ( ! inited_ ) ;

populate ( ) ;
inited_ = true ;
}

dio :: sol dio :: solve ( coeff sum )
{
assert ( inited_ ) ;

if ( sum < precomp_ . size ( ) )
return precomp_ [ sum ] ;

coeff st = precomp_ . size ( ) - max_coeff_ - 1 ;
coeff of = sum - st ;
coeff mx = of / max_coeff_ ;
coeff ix = of % max_coeff_ ;

return
dio :: sol
( precomp_ [ st + ix ] , max_coeff_ , mx ) ;
}

void dio :: populate ( )
{
precomp_ . push_back ( sol ( ) ) ;

coeff period_len = 0 ;
for
( coeff c = 1 ; period_len != max_coeff_ + 1 ; ++ c )
{
bool p ;

if ( coeffs_ . find ( c ) != coeffs_ . end ( ) )
p = pop_c ( c ) ;
else
p = pop ( c ) ;

if ( p )
++ period_len ;
else
period_len = 0 ;
}
}

bool dio :: pop_c ( coeff c )
{
precomp_ . push_back ( sol ( c ) ) ;
return true ;
}

bool dio :: pop ( coeff c )
{
sol solution ;
for
(
coeff_map_citr i_c = coeffs_ . begin ( ) ;
i_c != coeffs_ . end ( ) ; ++ i_c
)
{
coeff c_cand = ( * i_c ) . first ;

if ( c_cand >= c ) continue ;

sol s_cand
( precomp_ . at ( c - c_cand ) , c_cand ) ;

if ( s_cand < solution )
solution = s_cand ;
else
if ( s_cand == solution )
solution . add ( s_cand ) ;
}

precomp_ . push_back ( solution ) ;

return
( ! solution . is_sol ( ) ) ||
( solution . has ( max_coeff_ ) ) ;
}

dio :: sol :: sol ( coeff c )
: is_sol_ ( true ) , eff_ ( 1 )
{
coeff_map solution ;
solution [ c ] = 1 ;
s_ . push_back ( solution ) ;
}

dio :: sol :: sol ( const sol & s , coeff c , coeff i )
: is_sol_ ( s . is_sol ( ) ) , eff_ ( s . eff ( ) + i )
{
const sol_vec sols = s . s_ref ( ) ;
for
(
sol_vec_citr i_sol = sols . begin ( ) ;
i_sol != sols . end ( ) ; ++ i_sol
)
{
coeff_map solution = ( * i_sol ) ;
solution [ c ] += i ;
s_ . push_back ( solution ) ;
}
}

bool dio :: sol :: has ( coeff c ) const
{
if ( ! is_sol_ ) return false ;

for
(
sol_vec_citr i_sol = s_ . begin ( ) ;
i_sol != s_ . end ( ) ; ++ i_sol
)
{
const coeff_map & sol = ( * i_sol ) ;
if ( sol . find ( c ) == sol . end ( ) )
return false ;
}

return true ;
}

bool dio :: sol :: has ( const coeff_map & sol ) const
{
for
(
sol_vec_citr i_sol = s_ . begin ( ) ;
i_sol != s_ . end ( ) ; ++ i_sol
)
if ( sol == * i_sol ) return true ;

return false ;
}

void dio :: sol :: add ( const sol & s )
{
const sol_vec sols = s . s_ref ( ) ;
for
(
sol_vec_citr i_sol = sols . begin ( ) ;
i_sol != sols . end ( ) ; ++ i_sol
)
if ( ! has ( * i_sol ) )
s_ . push_back ( * i_sol ) ;
}
} ;

int main ( int argc , char * argv [ ] )
{
assert ( argc 3 ) ;

xyz :: dio :: coeff sum_from ;
xyz :: dio :: coeff sum_to ;

std :: string s_from ( argv [ 1 ] ) ;
std :: string s_to ( argv [ 2 ] ) ;
std :: istringstream iss_from ( s_from ) ;
std :: istringstream iss_to ( s_to ) ;

iss_from >sum_from ;
iss_to >sum_to ;

assert ( sum_from 0 ) ;
assert ( sum_to 0 ) ;
assert ( sum_to >= sum_from ) ;

xyz :: dio :: coeff_vec stamps ;

for ( xyz :: dio :: coeff i = 3 ; i != argc ; ++ i )
{
xyz :: dio :: coeff c ;

std :: string s_c ( argv [ i ] ) ;
std :: istringstream iss_c ( s_c ) ;

iss_c >c ;

assert ( c 0 ) ;

stamps . push_back ( c ) ;
}

xyz :: dio d ( stamps ) ;

d . init ( ) ;

for
(
xyz :: dio :: coeff sum = sum_from ;
sum != sum_to + 1 ; ++ sum
)
{
xyz :: dio :: sol solutions = d . solve ( sum ) ;

std :: cout << sum << std :: endl ;
std :: cout << "--------------------------------"
<< std :: endl ;
xyz :: dio :: sol_vec s = solutions . s_ref ( ) ;
std :: cout << "eff:" << solutions . eff ( ) << " sol:"
<< ( solutions . is_sol ( ) ? "yes" : "no" )
<< std :: endl ;
for
(
xyz :: dio :: sol_vec_citr is = s . begin ( ) ;
is != s . end ( ) ; ++ is
)
{
for
(
xyz :: dio :: coeff_map_citr ic =
( * is ) . begin ( ) ;
ic != ( * is ) . end ( ) ; ++ ic
)
std :: cout << " + " << ( * ic ) . first << " x "
<< ( * ic ) . second ;
std :: cout << std :: endl ;
}
std :: cout << "================================"
<< std :: endl ;
}
}

Trading off memory footprint for speed. If it does work,
it's probably the best algorithm overall unless some alpha
geek from sci.math can come up with something even better
that would be way beyond my understanding.

Test run excerpt:

pavel@debian:~/dev/cxx/t16$ time ./a.out 10000000 10000040 3 5 112
1113 10001 96732
10000000
--------------------------------
eff:126 sol:yes
+ 3 x 1 + 5 x 5 + 112 x 9 + 1113 x 5 + 10001 x 3 + 96732 x 103
================================
....
10000040
--------------------------------
eff:124 sol:yes
+ 3 x 3 + 5 x 3 + 1113 x 3 + 10001 x 13 + 96732 x 102
================================

real 0m7.761s
user 0m7.448s
sys 0m0.104s

--
Pavel Lepin

Mar 6 '07 #45

P: n/a
da******@brentwood.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.
I feel this has become somewhat of a contest. So, here is my entry (sorry, I
couldn't resist).

Beware that this will not do you any good for your assignment because the
algorithm (not the code) is way too cryptic (it uses two magic numbers and
cuts some corners). In fact, the proof of correctness has a few rather
subtle points. Elsethread, I have posted more helpful comments already.
Have fun figuring this one out:
#include <iostream>
#include <ostream>
#include <iomanip>
#include <utility>
#include <cassert>

struct solution {
unsigned no_9;
unsigned no_7;
unsigned no_2;
};

std::ostream & operator<< ( std::ostream & ostr,
solution const & sol ) {
ostr << std::setw(2)
<< sol.no_9 << " x 9c + "
<< sol.no_7 << " x 7c + "
<< sol.no_2 << " x 2c";
return ( ostr );
}

unsigned total ( solution sol ) {
return ( sol.no_9 + sol.no_7 + sol.no_2 );
}

int main ( void ) {
for ( unsigned money = 6; money < 200; ++money ) {
std::cout << std::setw(4) << money << "c";
solution try_a;
solution try_b;
// begin{white_magic}
try_a.no_2 = 0;
try_a.no_7 = ( 4 * ( money % 9 ) ) % 9;
try_a.no_9 = ( money - 7*try_a.no_7 ) / 9;
try_b.no_2 = ( 5 * ( money % 9 ) ) % 9;
try_b.no_7 = 0;
try_b.no_9 = ( money - 2*try_b.no_2 ) / 9;
// end{white_magic}
// begin{black_magic}
// The following asserts do fail sometimes.
// However, this does not affect correctness of the output.
// assert( money == 9 * try_a.no_9 + 7 * try_a.no_7 + 2 * try_a.no_2 );
// assert( money == 9 * try_b.no_9 + 7 * try_b.no_7 + 2 * try_b.no_2 );
// end{black_magic}
if ( total( try_a ) <= total( try_b ) ) {
std::cout << " = " << try_a;
}
if ( total( try_b ) <= total( try_a )
&&
try_b.no_9 != try_a.no_9 ) {
std::cout << " = " << try_b;
}
std::cout << '\n';
}
}
Of course, I do not endorse this style of programming. It just seemed to be
too much fun to miss out on this one. (On the plus side, I would think that
it should be very hard to implement a solution that is algorithmically more
efficient.)
Best

Kai-Uwe Bux
Mar 7 '07 #46

This discussion thread is closed

Replies have been disabled for this discussion.