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

补充：软件开发 , C++ ,