Re: C++ help

On Mar 4, 2:36 pm, "untitled" <awsra...@gmail.com> wrote:


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