30分,1、3、5AC求助
查看原帖
30分,1、3、5AC求助
477821
toolong114514楼主2023/4/3 11:45
#include<iostream>
using namespace std;
const int INF=0x3f3f3f3f;
int vita[30],fod[30][30],st[30],final_ans[30];
int v,g,minx=INF;
void dfs(int now,int all,int ans[30]){//ans暂存答案 
	bool flag=true;
	for(int i=1;i<=v;i++){
		if(vita[v]>0) flag=false;
	}//判断饲料是否够用 
	if(flag==true){
		if(all<minx){//按字典序 
			minx=all;
			for(int i=1;i<=all;i++){
				final_ans[i]=ans[i];
			}
		}
		return;//存储最小解 
	}
	for(int i=now+1;i<=g;i++){
		for(int j=1;j<=v;j++){
			vita[j]-=fod[i][j];
		}	
		ans[all+1]=i;
		dfs(i,all+1,ans);//选饲料 
		for(int j=1;j<=v;j++){
			vita[j]+=fod[i][j]; 
		}//回溯 
	}
} 
int main(){
	cin>>v;
	for(int i=1;i<=v;i++){
		cin>>vita[i];
	}
	cin>>g;  
	for(int i=1;i<=g;i++){
		for(int j=1;j<=v;j++){
			cin>>fod[i][j];
		}
	}
	dfs(0,0,st);//初始化 
	cout<<minx<<" ";
	for(int i=1;i<=minx;i++){
		cout<<final_ans[i]<<" ";
	}
	return 0;
}
2023/4/3 11:45
加载中...