求助,代码的一个小问题
查看原帖
求助,代码的一个小问题
810316
Qiluao楼主2023/7/22 15:38

dfs的剪枝当中,需要设置一个变量w记录浪费的木材。但是w的更新的判断条件我有个问题:为什么是a[i]<b[1]而不是a[i]<b[x+1}?(会有两个点WA)

bool dfs(int x,int l){//x表示还需要得到几块木板,l是木材店的剩余木材的开始下标
	if(x==0)//还需要0根木材,说明已经满足要求了,返回true
		return 1; 
	if(tot-w<sum[mid])//剪枝1
		return 0;
	bool f=0;
	for(int i=l;i<=m;i++){
		if(a[i]>=b[x]){//如果第i根木材可以满足约翰需要的第x根木材,则可以继续向下搜索 
		 	a[i]-=b[x];
		 	if(a[i]<b[1])
		 	//if(a[i]<b[x+1])
			 	w+=a[i];
		 	if(b[x-1]==b[x])
			 	f=dfs(x-1,i);//去重
		 	else
			 	f=dfs(x-1,1);	 	
		 	//f=dfs(x-1);
			if(a[i]<b[1])
		 	//if(a[i]<b[x+1])
			 	w-=a[i];
		 	a[i]+=b[x];
		 	if(f)
			 	return 1;
		}
	}
	return 0;
}
2023/7/22 15:38
加载中...