常規(guī)的回溯題
#include?<iostream>
#include?<fstream>
using?namespace?std;
ifstream?fin("holstein.in");
ofstream?fout("holstein.out");
#ifdef?_DEBUG
#define?out?cout
#define?in?cin
#else
#define?out?fout
#define?in?fin
#endif
int?data[15][25];
int?cur[25];
int?need[25];
bool?used[15];
int?res_cnt?=?INT_MAX;
bool?res[25];?
int?cnt?=?0;
int?v;
int?g;
void?backtracing(int?depth);
void?solve()
{
??in>>v;
??for(int?i=0;i<v;++i)
??????in>>need[i];
??in>>g;
??for(int?i=0;i<g;++i)
??????for(int?j=0;j<v;++j)
??????????in>>data[i][j];
??backtracing(0);
??out<<res_cnt;
??for(int?i=0;i<g;++i){
??????if(res[i])
??????????out<<"?"<<i+1;
??}
??out<<endl;
???????
}
void?add(int?idx)
{
????for(int?i=0;i<v;++i)
????????cur[i]+=data[idx][i];
}
void?remove(int?idx)
{
????for(int?i=0;i<v;++i)
????????cur[i]-=data[idx][i];
}
bool?isok()
{
????for(int?i=0;i<v;++i){
????????if(cur[i]<need[i])
????????????return?false;
????}
????return?true;
}
void?backtracing(int?depth)
{???
????//剪枝
???if(?cnt>=res_cnt?)?return;
????if(isok()){
????????if(cnt<res_cnt){
????????????res_cnt?=?cnt;
????????????memcpy(res,used,sizeof(used));
????????}
????????return;
????}
?
????if(depth>=g)?return;
????add(depth);
????used[depth]=true;
????cnt++;
????backtracing(depth+1);
????remove(depth);
????used[depth]=false;
????cnt--;
????backtracing(depth+1);
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 2844 KB]
Test 2: TEST OK [0.011 secs, 2840 KB]
Test 3: TEST OK [0.011 secs, 2844 KB]
Test 4: TEST OK [0.022 secs, 2840 KB]
Test 5: TEST OK [0.000 secs, 2844 KB]
Test 6: TEST OK [0.011 secs, 2844 KB]
Test 7: TEST OK [0.011 secs, 2840 KB]
Test 8: TEST OK [0.022 secs, 2844 KB]
Test 9: TEST OK [0.022 secs, 2840 KB]
Test 10: TEST OK [0.022 secs, 2840 KB]
All tests OK.