TopCoderの練習問題 BinPacking::minBins (SRM 598 div1 250)

　昨日、友達(id:kazy1991)に誘われてすごく久しぶりにやったTopCoderがそこそこに楽しかった。
　んで、なんか記事(http://kazy.hatenablog.com/entry/2013/12/04/225238)書いてはったので、便乗して解いてみた。

　さっきの友人の記事から問題を引用･･･

容量300のビンがあります． 100-300の大きさのアイテムがリストで渡されます.
ビンにアイテムを詰めるために少なくとも何本のビンが必要でしょうか

　一見簡単に見えるけど、どんな問題にも対応できるようにするととても神経を使います。
　例えば、

(150 , 150 , 150) --> 2　(300 , 150)
(100 , 100 , 100) --> 1　(300)

　そしてこれに気づけるかどうかでポイントが分かれそうな

(100 , 100 , 100 , 200 , 200 , 200) --> 3　(300 , 300 , 300)
【誤答例 : (100 , 100 , 100 , 200 , 200 , 200) --> 2　(300 , 200 , 200 , 200)】

　うーん(´・ω・｀)
　とりあえず書いてみたコードです↓

BinPacking.cpp

class BinPacking {
public:
    int minBins(vector <int> item) {
        
        int num_bin = 0 ;
        
        // 1. count up over 201
        for( auto it = item.end() ; it != item.begin() ; --it ) {
            if( (*it) > 200 ) {
                num_bin++ ;
                item.erase( it ) ;
            }
        }
        if( item.size()==0 ) return num_bin ;
        
        // 2. search the pear '100 and 200'
        while( true ) {
            auto it_100 = find( item.begin(), item.end(), 100) ;
            auto it_200 = find( item.begin(), item.end(), 200) ;
            if( it_100!=item.end() && it_200!=item.end() ) {
                num_bin++ ;
                item.erase( it_200 ) ;
                item.erase( it_100 ) ;
            }
            else {
                break ;
            }
        }
        if( item.size()==0 ) return num_bin ;
        
        // 3. search the pear '100 and 100 and 100'
        {
            int num_100 = 0 ;
            for( int i : item ) {
                if( i==100 ) num_100++ ;
            }
            
            int num_100_pear = num_100 / 3 ;
            for( int i=0 ; i<num_100_pear*3 ; i++ ) {
                item.erase( find( item.begin(), item.end(), 100) ) ;
            }
            num_bin += num_100_pear ;
        }
        if( item.size()==0 ) return num_bin ;
        
        // 4. search the pear 'sum of 2 item < 300'
        {
            sort(item.begin(), item.end(), std::greater<int>()) ;
            while( true ) {
                auto item_max = item.begin() ;
                
                // if find pear, put these to one bin
                bool f_match = false ;
                for( auto it = item_max+1 ; item_max!=item.end() ; ++it ) {
                    if( *it + *item_max <= 300 ) {
                        num_bin++ ;
                        item.erase( it ) ;
                        item.erase( item_max ) ;
                        f_match = true ; break ;
                    }
                }
                
                // if there is not pear, put one item to one bin
                if( !f_match ) {
                    num_bin++ ;
                    item.erase( item_max ) ;
                }
                
                if( item.size() < 2 ) {
                    if( item.size()==1 )
                        num_bin++ ;
                    break ;
                }
            }
        }
        
        return num_bin ;
    }
};

　手順というかアルゴリズムは･･･

1. 201以上のアイテムの数を数える　(count up over 201)
2. 100のアイテムと200のアイテムを探す　(search the pear '100 and 200')
3. 100のアイテム×３があるか探す　(search the pear '100 and 100 and 100')
4. 足しあわせて300以下になるアイテムを探す　(search the pear 'sum of 2 item < 300')

　です。
　どうしてもペアの見つからないアイテムは4で弾かれてカウントされています。

　せっかくだから解説書いてみようかな･･･
　でも250の問題だしドヤ顔で解説するのもなァ･･･

　要望があったら解説したいと思います。では！