UVa 624 - CD



#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef std::vector<int> vi;
typedef std::vector<pair<int, int> > vii;
#define FOR(l) for(vi::iterator it=l.begin();it!=l.end();it++)
#define FOR_L(l, s, e) for(vi::iterator it=l.begin()+s;it!=l.end()-e;it++)

//----------Main source code -----------------//
int n, t, mSpaceLeft, sum;
vi d, ans, state;
void rcr(int i){
 if(i==t){
  if(n<mSpaceLeft){
   ans.clear();
   mSpaceLeft = n;
   FOR(state)
    ans.push_back(*it);
  }
  return;
 }
 //track i not chosen
 rcr(i+1);
 //or chosen
 n-=d[i];
 state.push_back(d[i]);
 if(n>=0)
 rcr(i+1);
 n+=d[i];
 state.pop_back();
}
int main() {
 while(cin.good()&&cin>>n){
  cin>>t;
  mSpaceLeft = 99999999;
  d.resize(t, 0);
  for(int i=0;i<t;i++)
   cin>>d[i];
  rcr(0);
  sum=0;
  FOR(ans){
   cout<<*it<<" ";
   sum+=*it;
  }
  printf("sum:%d\n", sum);
 }
 return 0;
}
Runtime:0.045
Ideone: http://ideone.com/b3Ruvy

Comments

Popular Posts