深度优先搜索（DFS Depth-First-Search）

#include<bits/stdc++.h>
using namespace std;
const int maxn = 30;
int n,V,maxValue = 0;    //物品件数n，背包容量V，最大价值maxValue 
int w[maxn],c[maxn];     //w[i]为每件物品的重量，c[i]为每件物品的价值 
//DFS，index为当前处理的物品编号
//sumW和sumC为当前的总重量和总价值 
void DFS(int index,int sumW,int sumC){
	if(index == n) {     //达到递归边界，到达死胡同，完成对n件物品的选择 
		if(sumW<=V && sumC >= maxValue)
		{
			maxValue = sumC;
		}
		return ;
	}
	DFS(index+1,sumW,sumC);
	DFS(index+1,sumW+w[index],sumC+c[index]);   //每个index都有两种选择，
												//而且都会把后面的情况逐一运算 
	
	
}
int main(){
	scanf("%d%d",&n,&V);
	for(int i=0;i<n;i++){
		scanf("%d",&w[i]);
	}
	for(int i=0;i<n;i++){
		scanf("%d",&c[i]);
	}
	DFS(0,0,0);
	printf("%d\n",maxValue);
	return 0;
}

以上DFS算法由于每件物品都有两种选择，因此复杂度为O(2^n),这并不是很优秀，需要优化，上面代码总是把n件物品选完之后才去更新maxValue，但忽视了背包容量不超过V这个特点，完全可以把对sumW的判断加入“岔道口”中，只有小于V时才进入岔道口，效率回高很多。

void DFS(int index,int sumW,int sumC){
	if(index == n) {     

		return ;
	}
	DFS(index+1,sumW,sumC);
	if(sumW+w[index] <= V) {
		if(sumC+c[index] > maxValue)
		{
			maxValue = sumC + c[index];
		}
		DFS(index+1,sumW+w[index],sumC+c[index]);
	}
}

这种通过题目条件的限制来节省DFS计算量的方法叫做剪枝。剪枝是门艺术，可以使代码的计算量大大降低。