01リュックサックのDFS解法

01リュックサックは、M個の物品を取り出して空間Wのリュックサックにいくつか入れ、各物品の体積はW 1,W 2......Wnであり、それに対応する価値はP 1,P 2......Pnである.最大の価値を得る案を求める.

#include

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