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