常规的回溯题
#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.