回溯法

回溯法的基本思想

•“通用的解题法”，尤其适合求解一些组合数较大的问题。

•它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。

•算法搜索至解空间树的任一节点时，总是先判断该节点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该节点为根的子树的系统搜索，逐层向其祖先节点回溯。否则，进入该子树，继续按深度优先策略进行搜索。

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