使用DFS算法解决01背包问题

本文主要是介绍使用DFS算法解决01背包问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、时间复杂度为O(2^n)

void DFS(int index, int sumW, int sumC){
	if (index == n){
		if(sumW <= V && sumC > maxvalue){
			maxvalue = sumC;
		}
		return;
	}
	DFS(index+1,sumW,sumC);
	DFS(index+1,sumW+w[index],sumC+c[index]);
}

二、“剪枝”

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]);
	}
}

int main(){
	cin >> n >> V;
	for (int i = 0; i < n; i++)
	cin >> w[i];
	
	for (int i = 0; i < n; i++)
	cin >> c[i];
	
	DFS(0,0,0);
	cout << maxvalue;
	
	return 0;
}

这篇关于使用DFS算法解决01背包问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！