回溯法
回溯法的基本思想
•“通用的解题法”，尤其适合求解一些组合数较大的问题。
•它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。
•算法搜索至解空间树的任一节点时，总是先判断该节点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该节点为根的子树的系统搜索，逐层向其祖先节点回溯。否则，进入该子树，继续按深度优先策略进行搜索。
image.png
image.png
解空间树的动态搜索
•从根结点出发，沿着它的儿子结点向下搜索：
–如果它和儿子结点的边所标记的分量xi满足约束条件和目标函数的界（ 即有可能产生最优解），就把分量xi加入到它的部分解中，并继续向下搜索以儿子结点作为根的子树；
–如果它和儿子结点的边所标记的分量xi不满足约束条件或目标函数的界，就结束对儿子结点作为根的子树的搜索，选择对另一个儿子结点作为根的子树进行搜索。
–剪枝函数
•用约束函数在扩展结点处剪去不满足约束的子树（剪去不可行）
•用限界函数剪去不能得到最优解的子树（剪去非最优）
回溯法的基本步骤
1.针对所给问题，定义问题的解空间；
2.确定易于搜索的解空间树；
3.以深度优先的方式搜索解空间树，并且在搜索过程中用剪枝函数避免无效搜索。
•用约束函数考察是否可行
•用限界函数考察是否（有可能）最优
0-1背包问题
image.png
// 回溯法——0-1背包.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Item
{
int id;
float value;
float weight;
float v_w;
};
const int maxn = 1000;
bool isChosen[maxn];
vector<Item>item;
vector<int>x;
int n;//物品数量
int c;//背包最大容量
int cw = 0;//cw为当前重量
int cv = 0;//cv为当前价值
int bestv = 0;//bestv为当前最优价值
float Bound(int i)//限界函数
{
float cleft = c - cw;//计算剩余容量
float bound = cv;
//用贪心算法求解背包问题的方法来计算限界函数，这里求出的bound是略大于最优解的值（也有可能就是最优解）
while (i<=n&&item[i].weight<=cleft)
{
cleft -= item[i].weight;
bound += item[i].value;
i++;
}
if (i <= n)
{
bound = bound + item[i].value * (cleft / item[i].weight);
}
return bound;
}
void Knapsack_Backtrack(int i)
{
if (i > n)
{
bestv = cv;
memset(isChosen, false, n + 1);
for (int j = 1;j <= n;j++)
{
if (x[j])
isChosen[j] = true;
}
return;
}
if (cw + item[i].weight <= c)
{
cv += item[i].value;
cw += item[i].weight;
x[i] = 1;
Knapsack_Backtrack(i + 1);
cv -= item[i].value;
cw -= item[i].weight;
}
//左子树搜索完，恢复状态，准备判断是否搜索右子树
int bound = Bound(i+1);
if (bound > bestv)//回溯,搜索右子树
{
x[i] = 0;
Knapsack_Backtrack(i + 1);
}
}
bool cmp(Item a, Item b)
{
if (a.v_w > b.v_w)
return true;
else
return false;
}
int main()
{
cin >> n >> c;
float value, weight;
item.resize(n + 1);
x.resize(n + 1);
for (int i = 1;i <= n;i++)
{
cin >> value >> weight;
item[i]={ i+1,value,weight,value / weight };//存储物品信息
}
sort(item.begin()+1, item.end(), cmp);
Knapsack_Backtrack(1);
for (int i = 1;i <= n;i++)
{
if (isChosen[i])
{
cout << "选择物品为：" << i << " ";
}
}
cout << "\n";
cout << "最大价值为" << bestv << endl;
return 0;
}
image.png
