回溯：0-1背包问题(回溯+剪枝)

回溯

0-1背包问题(回溯+剪枝)

#include
#define N 3	//物品种类 
#define W 5	//背包重量 
using namespace std;
int choose[N];
int bestchoose[N];
int w[N]={1,2,3};	//物品重量 
int v[N]={6,12,10}; //物品价值 
int bbW=0,bbV=0;//当前背包重量，价值 
int maxV=0;//最大价值
 
void output(){
	if(bbV>maxV){
		maxV=bbV;
		for(int i=0;i=w[i]){//剪枝，选第i种物品
		choose[i]=1;
		bbW+=w[i];
		bbV+=v[i];
		dfs(i+1);
		choose[i]=0;//回溯
		bbW-=w[i];
		bbV-=v[i];
	}
	choose[i]=0;//不选第i种物品;
	dfs(i+1);
}

void print(){
	for(int i=0;i