01背包的DFS解法

01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。

#include<stdio.h>

struct t
{
	int wi;
	int vi;
}t[105];

int n,c;
int max=0;
void DFS(int q,int dw,int dv)
{
	if(q==n)
	{
		if(dw<=c && dv>max)//将所有满足条件的进行筛选，找到最大加和；
			max=dv;
		return ;
	}
	dw+=t[q].wi;
	dv+=t[q].vi;
	DFS(q+1,dw,dv);//选取当前物品后继续向后增加
	dw-=t[q].wi;
	dv-=t[q].vi;
	DFS(q+1,dw,dv);//不选当前物品向后增加
}

int main()
{
	scanf("%d%d",&n,&c);
	int i,j;
	for(i=0;i<n;i++)
		scanf("%d%d",&t[i].wi,&t[i].vi);
	DFS(0,0,0);
	printf("%d ",max);
	return 0;
}