9分
查看原帖
9分
1137536
jc_artcle楼主2024/9/11 21:15

rt

#include<bits/stdc++.h>
using namespace std;
int v,g,w[33],l[22][33],p=2147483647,as[22],sm[33],us[22];
bool ck()
{
	memset(sm,0,sizeof(sm));
	for(int i=1;i<=g;i++) if(us[i]) for(int j=1;j<=v;j++) sm[j]+=l[i][j];
	for(int i=1;i<=v;i++) if(sm[i]<w[i]) return 0;
	return 1;
}
void dfs(int stp)
{
	if(stp>g)
	{
		if(ck())
		{
			int ct=0;
			for(int i=1;i<=g;i++) ct+=us[i];
			if(ct<=p)
			{
				int cr=0;
				p=ct;
				for(int i=1;i<g;i++) if(us[i]) as[++cr]=i;
			}
			return;
		}
	}
	for(int i=0;i<=1;i++) 
	{
		us[stp]=i;
		dfs(stp+1);
	}
}
int main(){
	cin>>v;
	for(int i=1;i<=v;i++) cin>>w[i];
	cin>>g;
	for(int i=1;i<=g;i++) for(int j=1;j<=v;j++) cin>>l[i][j];
	dfs(1);
	cout<<p<<' ';
	for(int i=1;i<=p;i++) cout<<as[i]<<' ';
	return 0;
}
2024/9/11 21:15
加载中...