第四周_算法提高_01背包

#include<iostream> 
#include<cstring>
using namespace std;
int array[210][3];
int array1[210][2];
int n,m,MAX=0;
int w=0,v=0,temp=0;
void search(int step){
	cout<<"search"<<temp++<<endl;
	w=0;
	for(int j=0;j<n;j++){
		w+=array1[j][0];
	}
	if(w<m){
		if(step>=n){
			v=0;
			for(int j=0;j<n;j++){
				v+=array1[j][1];
			}				
			if(v>MAX){
				MAX=v;
			}
		}
		for(int i=0;i<n;i++){
			if(array[i][2]==0){
				array[i][2]=1;
				array1[step][0]=array[i][0];
				array1[step][1]=array[i][1];
				search(step+1);				
				array[i][2]=0;
				array1[step][0]=0;
				array1[step][1]=0;
				v=0;
				for(int j=0;j<n;j++){
					v+=array1[j][1];
				}				
				if(v>MAX){
					MAX=v;
				}
			}
		}
	}
	else if(w==m){
		v=0;
		for(int j=0;j<n;j++){
			v+=array1[j][1];			
		}		
		if(v>MAX){
			MAX=v;
		}
	}
	
}
int main(){
	memset(array,0,sizeof(array));
	memset(array1,0,sizeof(array1));
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>array[i][0]>>array[i][1];
	}
	search(0);
	cout<<MAX;
	return 0;
}