c++实现回溯算法背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
using namespace std;
int weight[4] = { 1,2,3,4 };
int value[4] = { 3,2,4,3 };
int flag[4] = { 0 };
int maxvalue = 0;
int packweight = 0;
int packvalue = 0;
void backtrack(int node)
{
	if (node == 4)
	{
		if (maxvalue < packvalue)
		{
			maxvalue = packvalue;
		}
	}
	else
	{
		for (int i = 0; i < 2; i++)
		{
			if (i == 0)
			{
				backtrack(node + 1);
			}
			else
			{
				if (packweight + weight[node] <= 8)//小于背包总容量
				{
					packweight += weight[node];
					packvalue += value[node];
					backtrack(node + 1);//继续进行深度搜索
					packweight -= weight[node];//把当前物品从背包中删除，
					packvalue -= value[node];//因为计算下一条路径时需要把前一次的清空
				}
			}
		}
	}
}
int main()
{
	backtrack(0);
	cout << "背包的最大价值：" << maxvalue;
}