C++ help

[davy.zou]

then its an easy one,

x is the requested number

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

just put it in c code

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

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

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

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

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

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

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

Six, what is if final out put?

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

Davy

 

[davy.zou]

then its an easy one,

x is the requested number

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

just put it in c code

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

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

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

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

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

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

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

Six, what is if final out put?

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

Davy

 

[Alan Johnson]

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 < n of 1 + C(n - d)

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)
for i = 1 to k
if (d <= k)
value = 1 + C[v - d]
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]

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 < n of 1 + C(n - d)

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)
for i = 1 to k
if (d <= k)
value = 1 + C[v - d]
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]]

 

[Alan Johnson]

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 < n of 1 + C(n - d)

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)
for i = 1 to k
if (d <= k)

Gah. One more correction. This should have been:
if (d <= v)

value = 1 + C[v - d]
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.

 

[untitled]

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.

 

[untitled]

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;
}

 

[roy axenov]

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 ; }

 

[Kai-Uwe Bux]

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

 

[el3anchoke]

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;
}

 

[Chris Thomasson]

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;
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]

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;
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]

I know what's missing...

#include <cstdio>


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

 

[Howard]

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]

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]

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_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]

[...]

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

What about the one I posted here:

http://groups.google.com/group/comp.lang.c++/msg/f29519253ff80cdf

?

 

[Kai-Uwe Bux]

What about the one I posted here:

http://groups.google.com/group/comp.lang.c++/msg/f29519253ff80cdf

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

 

[Chris Thomasson]

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;
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]

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

instead of

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



Best

Kai-Uwe Bux