求助,dfs50分,不知道该咋剪枝
查看原帖
求助,dfs50分,不知道该咋剪枝
518995
GUMIfans0626楼主2022/6/12 09:58
#include<bits/stdc++.h>
using namespace std;
int v,g;
int cow[30],grass[30][30],temp[30];
int ans=99999999;
bool tl[30];
int answer[30];
int trueanswer[30];
void dfs(int deep,int now){
	if(now>=ans){
		return;
	}
	if(deep>g){
		for(int i=1;i<=v;i++){
			if(temp[i]>0){
				return;
			}
		}
		ans=min(ans,now);
		for(int i=1;i<=g;i++){
			trueanswer[i]=answer[i];
		}
		return;
	}
	for(int i=1;i<=g;i++){
		if(tl[i]==0){
			tl[i]=1;
			answer[deep]=i;
			for(int j=1;j<=v;j++){
				temp[j]-=grass[i][j];
			}
			dfs(deep+1,now+1);
			answer[deep]=0;
			for(int j=1;j<=v;j++){
				temp[j]+=grass[i][j];
			}
			dfs(deep+1,now);
			tl[i]=0;
		}
	}
}
int main(){
	cin>>v;
	for(int i=1;i<=v;i++){
		cin>>cow[i];
		temp[i]=cow[i];
	}
	cin>>g;
	for(int i=1;i<=g;i++){
		for(int j=1;j<=v;j++){
			cin>>grass[i][j];
		}
	}
	dfs(1,0);
	cout<<ans<<" ";
	for(int i=1;i<=g;i++){
		if(trueanswer[i]==0){
			continue;
		}else{
			cout<<trueanswer[i]<<" ";
		}
	} 
	return 0;
} 
2022/6/12 09:58
加载中...