457,911 Members | 1,274 Online 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
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

 P: n/a here is the code I first came up with, obviously it doesn't work, #include #include 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: "<>cents; if (cents<0) { cout<<"Error."<

 P: n/a On 3 Mar, 23:02, davy....@brentwood.bc.ca wrote: On Mar 3, 5:55 pm, Ian Collins

 P: n/a On Mar 3, 6:23 pm, "Gavin Deane"

 P: n/a 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" 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: here is the code I first came up with, obviously it doesn't work, 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 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"

 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

 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

 P: n/a On Mar 3, 9:54 pm, Alan Johnson

 P: n/a On Mar 3, 9:39 pm, "untitled"

 P: n/a On Mar 3, 9:39 pm, "untitled"

 P: n/a On Mar 3, 9:39 pm, "untitled"

 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 // Now compute C(1) through C(n) for v = 1 to n // maybe something like std::numeric_limits::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 byuser? If it is inputed by user, then it shouldn't be too difficult toadd the lines of codes to the program that will assign the user inputto 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 // Now compute C(1) through C(n) for v = 1 to n // maybe something like std::numeric_limits::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 byuser? If it is inputed by user, then it shouldn't be too difficult toadd the lines of codes to the program that will assign the user inputto D1 through Dk.Davy You can expand the recurrence I posted earlier in this thread to anynumber of denominations. So if I had an array of denominations d.C(n) = 0 if n = 0C(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 // Now compute C(1) through C(n) for v = 1 to n // maybe something like std::numeric_limits::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 wewant. The array S keeps up with the index of which denomination stampwe add at each step. We can use that knowledge to construct theactual 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 thefirst place. At each step we are just subtracting the denominationthat we decided was necessary to add to the optimal substructure toget 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"

 P: n/a On Mar 4, 1:36 pm, "untitled" #include 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"<>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) && (sevenstwos)) { sevens=sevens-twos; nines=twos; twos=0; } cout<<"twos="<

 P: n/a On Mar 4, 2:36 pm, "untitled" wrote: int sevens=x/7 remainder=x - (sevens*7) int twos= remainder/2 if (remainder - (twos*2)) =1 then twos++ if sevens != 0 && sevens #include #include 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" On Mar 4, 5:35 am, davy....@brentwood.bc.ca wrote: On Mar 3, 9:39 pm, "untitled" #include 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"<>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) && (sevenstwos)) { sevens=sevens-twos; nines=twos; twos=0; } cout<<"twos="<

 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 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 = 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" >I have started learning c++ and I need help. I need to write aprogram, the question is as follows.At a post office, there are a certain number of 2, 7, and 9centsstamps, now, given a total number of cents required, find the correctand most effective combination of stamps.meaning that if you were to need 14cents, the correct output should be2 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 = 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 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" >here is the code I first came up with, obviously it doesn't work, Think about dividing the available amount by 9, 7 and 2 in that order. Iam not sure that is the right answer in all cases, but you can expand onit 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" osmium wrote: >>Think about dividing the available amount by 9, 7 and 2 in that order. Iam not sure that is the right answer in all cases, but you can expand onit if needed. [snip] I am not so sure that this looks like a promissing line of attack. Thereseems to be a little more to the problem. What is the answer for 10 andhowdo 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" On Mar 4, 5:35 am, davy....@brentwood.bc.ca wrote: On Mar 3, 9:39 pm, "untitled" wrote: int sevens=x/7 remainder=x - (sevens*7) int twos= remainder/2 if (remainder - (twos*2)) =1 then twos++ if sevens != 0 && sevens #include #include 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 = 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 On Mar 5, 3:54 am, Kai-Uwe Bux #include #include 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" >That is, your program tells me: 35c = 3 x 9c + 1 x 7c + 0 x 2c + changewhich, I think, is not what the OP's assignment asked for. I wouldgatherthat 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 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 thisthread. But it really gets a little slow on largernumbers. 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 #include #include #include #include #include #include #include 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 #include #include #include #include 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. 