回溯函数的模板为
void backtrack(int t) { if (t > n) output(x); else for (int i = 0; i <= 1; i++) { x[t] = i; if (constraint(t) && bound(t)) //constraint(t)为约束函数，bound(t)为限界函数 backtrack(t + 1); } }代码如下
#include <iostream> using namespace std; #define N 100 int w[N]; //每个物品的重量 int v[N]; //每个物品的价值 int x[N]; //x[i]=1：物品i放入背包，0代表不放入 int n, c; //n：一共有多少物品，c：背包的最大容量 int CurWeight = 0; //当前放入背包的物品总重量 int CurValue = 0; //当前放入背包的物品总价值 int BestValue = 0; //最优值；当前的最大价值，初始化为0 int BestX[N]; //最优解；BestX[i]=1代表物品i放入背包，0代表不放入 void backtrack(int t)//参数t表示当前处在第几层做抉择，t=n时表示当前在决定是否将第n个物品放入背包 { if (t > n)//叶子节点，输出结果 { if (CurValue > BestValue)//如果找到了一个更优的解 { BestValue = CurValue;//保存更优的值和解 for (int i = 1; i <= n; ++i) BestX[i] = x[i]; } } else { for (int i = 0; i <= 1; ++i)//遍历当前节点的子节点：0 不放入背包，1放入背包 { x[t] = i; if (i == 0) //不放入背包 { backtrack(t + 1); } else //放入背包 { if ((CurWeight + w[t]) <= c)//约束条件：背包目前可以容纳这个物品 { CurWeight += w[t]; CurValue += v[t]; backtrack(t + 1); CurWeight -= w[t]; CurValue -= v[t]; } } } } } int main() { cout << "请输入物品的个数：" << endl; cin >> n; cout << "请输入每个物品的重量 " << endl; for (int i = 1; i <= n; i++) cin >> w[i]; cout << "请输入每个物品的价值 " << endl; for (int i = 1; i <= n; i++) cin >> v[i]; cout << "请输入背包的容量：" << endl; cin >> c; backtrack(1);//t=1表示当前在决定是否将第一个物品放入背包 cout << "最优值是:" << BestValue << endl; for (int i = 1; i <= n; i++) cout << BestX[i] << " "; return 0; }