编辑代码

#include <iostream>
using namespace std;


#define N 5   //默认有4个物品。第一个不使用
int w[N] = {6, 5, 4, 2, 1};  //每个物品的重量
int v[N] = {5, 3, 5, 3, 2};  //每个物品的价值
int x[N];     //x[i]=1：物品i放入背包，0代表不放入
int n = 5, c = 10;  //n：一共有多少物品，c：背包的最大容量

int SumWeight = 0;  //当前放入背包的物品总重量
int SumValue = 0;   //当前放入背包的物品总价值

int OptimalValue = 0;  //最优价值；当前的最大价值，初始化为0
int OptimalSolution[N];       //最优解；OptimalSolution[i]=1代表物品i放入背包，0代表不放入

/*
*回溯算法 参数t表示当前处在第几层做抉择，t=1时表示当前在决定是否将第一个物品放入背包
*/
void backtracking(int t) {
	//叶子节点，输出结果
	if (t > n) {
		//如果找到了一个更优的解
		if (SumValue > OptimalValue) {
			//保存更优的值和解
			OptimalValue = SumValue;
			for (int i = 1; i <= n; ++i)
				OptimalSolution[i] = x[i];
		}
	} else {
		//遍历当前节点的子节点：0 不放入背包，1放入背包
		for (int i = 0; i <= 1; ++i) {
			x[t] = i;

			if (i == 0) { //不放入背包
				backtracking(t + 1);
			} else { //放入背包
				//约束条件：当前物品是否放的下
				if ((SumWeight + w[t]) <= c) {
					SumWeight += w[t];
					SumValue += v[t];
					backtracking(t + 1);
					SumWeight -= w[t];
					SumValue -= v[t];
				}
			}
		}
	}
}

int main() {
	backtracking(1);

	cout << "最优价值是:" << OptimalValue << endl;
	cout << "(";
	for (int i = 1; i <= n; i++)
		cout << OptimalSolution[i] << " ";
	cout << ")";
	return 0;
}