Velocity Reviews > C++ > C++ help

C++ help

Chris Thomasson
Guest
Posts: n/a

 03-04-2007
<(E-Mail Removed)> wrote in message
news:(E-Mail Removed) 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 STAMP_STATICINIT() \
{STAMP_BASE_PRICE(), 7, 9, 12, 19, 25, 50}

{48, 11, 1, 74, 3, 8, 14, 23, 33, 13, 123, 87}

int main() {
int i;
int const stamps[STAMP_DEPTH()] = STAMP_STATICINIT();

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

printf("-- press <ENTER> to 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? :^)

Chris Thomasson
Guest
Posts: n/a

 03-04-2007
"Chris Thomasson" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed). ..
> <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed) 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 STAMP_STATICINIT() \
{STAMP_BASE_PRICE(), 7, 12, 15, 18, 25, 32}

{248, 211, 1, 274, 122, 143, 214, 176, 87, 213, 323, 587}

int main() {
int i;
int const stamps[STAMP_DEPTH()] = STAMP_STATICINIT();

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

printf("-- press <ENTER> to 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

Chris Thomasson
Guest
Posts: n/a

 03-04-2007
I know what's missing...

#include <cstdio>

printf tend to get crabby when its used and there is nobody around to
declare it!

Howard
Guest
Posts: n/a

 03-04-2007

"Kai-Uwe Bux" <(E-Mail Removed)> wrote in message
news:esd2hk\$cvc\$(E-Mail Removed)...
> osmium wrote:
>
>> <(E-Mail Removed)> wrote:
>>
>>> 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

Kai-Uwe Bux
Guest
Posts: n/a

 03-04-2007
Howard wrote:

>
> "Kai-Uwe Bux" <(E-Mail Removed)> wrote in message
> news:esd2hk\$cvc\$(E-Mail Removed)...
>> osmium wrote:
>>
>>> <(E-Mail Removed)> wrote:
>>>
>>>> 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

Kai-Uwe Bux
Guest
Posts: n/a

 03-05-2007
roy axenov wrote:

> On Mar 4, 2:36 pm, "untitled" <(E-Mail Removed)> wrote:
>> On Mar 4, 5:35 am, (E-Mail Removed) wrote:
>> > On Mar 3, 9:39 pm, "untitled" <(E-Mail Removed)>
>> > 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
> 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_group> time 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

Chris Thomasson
Guest
Posts: n/a

 03-05-2007
[...]

> Nice, the first correct solution I have seen in this thread.

What about the one I posted here:

?

Kai-Uwe Bux
Guest
Posts: n/a

 03-05-2007
Chris Thomasson wrote:
> What about the one I posted here:
>

After changing the constants so that they actually match the problem of the
OP:

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

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

{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 (

checking stamp price of (7) against remainder (
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

Chris Thomasson
Guest
Posts: n/a

 03-05-2007
> 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 STAMP_STATICINIT() \
{STAMP_BASE_PRICE(), 7, 9 }

{35, 100}

int main() {
int i;
int const stamps[STAMP_DEPTH()] = STAMP_STATICINIT();

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

printf("-- press <ENTER> to 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?

Kai-Uwe Bux
Guest
Posts: n/a

 03-05-2007
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 STAMP_STATICINIT() \
> {STAMP_BASE_PRICE(), 7, 9 }
>
> {35, 100}
>
>
> int main() {
> int i;
> int const stamps[STAMP_DEPTH()] = STAMP_STATICINIT();
>
> for(i = 0; i < BUYOFFERS_DEPTH(); ++i) {
> int x, p, r;
> int remainder = base;
>
> printf("-- press <ENTER> to 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_group> a.out
-- press <ENTER> to 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 <ENTER> to 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)

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

Best

Kai-Uwe Bux