[dfs]zoj 3631：Watashi's BG

大致题意：

    总共有m块钱(m<10000000)，有n件物品(n<30)，每件都有一定的价格。求怎么样选择买的物品才能使得价格总和不超过m，且花钱最多。

 

大致思路：

    背包应该会超时，因为m过大，这里用dfs来解决～～。

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int num[50];
int n,m,res;

bool cmp(int a,int b){
	return a>b;
}

void dfs(int loc,int sum){
	if(sum>m)return;
	if(loc==n){
		res=max(sum,res);
		return;
	}
	int i,a=sum;
	for(i=loc;i<n;i++){
		a+=num[i];
	}
	if(a<=res)return;
	dfs(loc+1,sum+num[loc]);
	dfs(loc+1,sum);
}

int main(){
	int i,j,a,b,c;
	while(scanf("%d%d",&n,&m)!=EOF){
		res=0;
		for(i=0;i<n;i++){
		    scanf("%d",&num[i]);
		}
		sort(num,num+n,cmp);
		dfs(0,0);
		printf("%d\n",res);
		//cout<<res<<endl;
	}
	return 0;
}