PKU 1010

STAMPS
可能な切手の組み合わせをバックトラックで生成する。
コードが長くなってくるとバグが増える……。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> stamp, custom;
vector<int> number;     //  number of each stamps
int         type;       //  number of different types
int         total;      //  total number of stamps
vector<int> best;       //  best combination
int         besttype;   //  nmaximum number of different types
int         besttotal;  //  total number of stamps in best combination
bool        tie;        //  whether there area tied combinations
int         rest;       //  rest of postage

void        select( int s );
int         compare();

int main()
{
    while ( true )
    {
        //  input
        int n;

        stamp.clear();
        while ( cin >> n  &&  n > 0 )
            stamp.push_back( n );

        custom.clear();
        while ( cin >> n  &&  n > 0 )
            custom.push_back( n );

        if ( stamp.size() == 0 )
            break;

        //  solve
        number.resize( stamp.size() );

        for ( int i=0; i<(int)custom.size(); i++ )
        {
            besttype = 0;
            tie = false;
            rest = custom[i];

            select( 0 );

            //  display
            cout << custom[i];

            if ( besttype == 0 )
                cout << " ---- none";
            else
            {
                cout << " (" << besttype << "):";

                if ( tie )
                    cout << " tie";
                else
                {
                    for ( int j=0; j<(int)best.size(); j++ )
                        for ( int k=0; k<best[j]; k++ )
                            cout << " " << stamp[j];
                }
            }

            cout << endl;
        }
    }

    return 0;
}

//  set the number of s-th stamp and make the recursive call
void select( int s )
{
    if ( rest == 0 )
    {
        switch ( compare() )
        {
        case 1:
            best = number,
            besttype = type,
            besttotal = total;
            tie = false;
            break;
        case 0:
            tie = true;
            break;
        }
        
        return;
    }

    if ( total >= 4  ||
         s >= (int)stamp.size() )
        return;

    for ( int i=0; i<=rest/stamp[s] && total+i<=4; i++ )
    {
        number[s] = i;
        if ( i > 0 )  type++;
        rest -= i * stamp[s];
        total += i;

        select( s + 1 );

        number[s] = 0;
        if ( i > 0 )  type--;
        rest += i * stamp[s];
        total -= i;
    }
}

//  compare "number" and "best"
//   1: "number" is better
//   0: tie
//  -1: "best" is better
int compare()
{
    if ( type > besttype )  return 1;
    if ( type < besttype )  return -1;

    if ( total < besttotal )  return 1;
    if ( total > besttotal )  return -1;

    int ht = 0;
    for ( int i=0; i<(int)number.size(); i++ )
        if ( number[i] > 0 )
            ht = max( ht, stamp[i] );

    int hb = 0;
    for ( int i=0; i<(int)best.size(); i++ )
        if ( best[i] > 0 )
            hb = max( hb, stamp[i] );

    if ( ht > hb )  return 1;
    if ( ht < hb )  return -1;

    return 0;
}