Poj Solution 3211

http://poj.org/problem?id=3211

#include <stdio.h>
#include <vector>
#include <string>
#include <set>
using namespace std;

vector<int> v[10];
string color[10];
set<int> s;

int main( ) {
    int n, m, i, j, ans, sum, t, best;
    char w[100];
    while( scanf( "%d%d", &m, &n ) == 2 && ( n || m ) ) {
        
        for( i=0; i<m; i++ ) {
            scanf( "%s", w );
            color[i] = w;
            v[i].clear( );
        }

        for( i=0; i<n; i++ ) {
            scanf( "%d %s", &t, w );
            for( j=0; j<m; j++ )
                if( color[j] == w )
                    break;
            v[j].push_back( t );
        }
        
        set<int>::reverse_iterator it;
        ans = 0;

        for( i=0; i<m; i++ ) {
            s.clear();
            s.insert( 0 );
            sum = 0;

            for( j=0; j<v[i].size(); j++ ) {
                for( it = s.rbegin(); it != s.rend(); it++ ) {
                    if( s.find( t=*it+v[i][j] ) == s.end() )
                        s.insert( t );
                }
                sum += v[i][j];
            }

            best = sum;

            for( it = s.rbegin(); it != s.rend(); it++ ) {
                t = *it;
                if( sum - t > t )
                    t = sum - t;
                if( best > t )
                    best = t;
            }
            ans += best;
        }

        printf( "%dn", ans );
    }
    return 0;
}