刘星辰liuxingchen • 1年前
#include<bits/stdc++.h>
using namespace std;
int n;
int a[30];
int m;
int b[20][30];
int path[30];
int Min=INT_MAX;
vector<int> Path;
vector<int> ans;
bool abc()
{
for(int i=1;i<=n;i++)
{
if(path[i]<a[i])
{
return 0;
}
}
return 1;
}
void dfs(int now,int MIN)
{
if(abc()==1)
{
if(now<Min)
{
Min=now;
ans.clear();
for(int i=0;i<Path.size();i++)
{
ans.push_back(Path[i]);
}
}
return ;
}
for(int i=MIN;i<=m;i++)
{
Path.push_back(i);
for(int j=1;j<=n;j++)
{
path[j]+=b[i][j];
}
dfs(now+1,i+1);
Path.pop_back();
for(int j=1;j<=n;j++)
{
path[j]-=b[i][j];
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
cin>>m;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
cin>>b[i][j];
}
}
dfs(0,1);
cout<<Min;
cout<<" ";
for(int i=0;i<ans.size();i++)
{
cout<<ans[i];
cout<<" ";
}
return 0;
}
评论: