UVa 624: CD

這道題由於每組數據最多只有20個，其可能組成的時間總長度最多有2^20大約10^6中，一個數組可以放下，我使用了vector。   選出vector中存有的總時間長度的最大者（且不超過N），根據其序號計算出該最大時間總長度包含了哪些數據即可。   我的解題代碼如下：

 
#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <cstdlib>  
#include <vector>  
#include <algorithm>  
using namespace std;  
  
#define maxm 20  
int Duration[maxm];  
  
int main()  
{  
    int N,M;  
    int Size,Max,Maxk;  
    int tmp;  
    vector<int> v;  
    while(cin >> N >> M)  
    {  
        for(int i=0; i<M; i++) cin >> Duration[i];  
        Max = 0;  
        v.clear(); v.push_back(0);  
  
        for(int i=0; i<M; i++)  
        {  
            Size = v.size();  
            for(int j=0; j<Size; j++)  
            {  
                v.push_back( tmp = v[j]+Duration[i]);  
                if(tmp<=N && Max<tmp)  
                {  
                    Max = tmp;  
                    Maxk = v.size()-1;  
                }  
            }  
        }  
  
        int div = 2;  
        for(int i=0; i<M; i++)  
        {  
            if(Maxk%div >= div/2) cout << Duration[i] << ' ';  
            div *= 2;  
        }  
        cout << "sum:" << Max << endl;  
    }  
      
    return 0;  
}