NEFU-2023-算法设计与分析实验四回溯算法设计

港控/mmm° 2024-04-17 11:43 68阅读 0赞

## 作者的话 ##

**大底包含了算法硬性规定的作业代码，并非最优解，仅供参考并会持续更新。勿要无脑copy，对自己负责。如果代码有误或者优化建议，直接相应博客下方评论或者qq找我如果对代码有理解不了的或者疑惑可以询问我，但是请确保你已经自己思考过或者查过搜索引擎（如果我原模原样搜到了资料的话我会锤你的hh）。一些语法和库的资料查询网站受个人风格影响，部分题目解题方式可能没按照教学要求，如有必要请自己按教学要求做一遍。如果可以的话，麻烦借鉴完以后给我博客来个三连啥的，这可能对我以后找工作或者其他博客的推广什么的有些帮助，感谢**

如要系统学习可看我的另一篇博客[算法小课堂(六)回溯算法][Link 1]

## 题目一**0-1背包问题** ##

> 有N件物品和一个容量为V的背包。第i件物品的重量是w\[i\]，价值是v\[i\]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。要求每个物品要么放进背包，要么不放进背包。

#### 实验书模板 ####

#include<iostream>
    using namespace std;
    int n, t;//n是物品个数
    double C;//背包容量
    double w[105];//重量
    double v[105];//价值
    double p[105];//物品单位价值
    int BestX[105];//最合适的序号合适为1不合适为0
    int X[105];//现阶段最合适的序号
    int order[100];//记录下那个序号在knapsack的时候进行过交换
    double CurWeight = 0.0;//现阶段背包物品的重量
    double CurValue = 0.0;//现阶段背包物品的价值
    double BestValue = 0.0;//背包物品的最大价值
    void knapsack()//将物品按照单位重量价值排序；
    {
        int temporder = 0;
        double temp = 0.0;
        for (int i = 1; i <= n; i++)
            p[i] = v[i] / w[i];//物品价值/物品重量
        for (int i = 1; i <= n - 1; i++)
        {
            for (int j = i + 1; j <= n; j++)
                if (p[i] < p[j])
                {
                    temp = p[i];
                    p[i] = p[j];
                    p[j] = temp;
                    temporder = order[i];
                    order[i] = order[j];
                    order[j] = temporder;
                    temp = v[i];
                    v[i] = v[j];
                    v[j] = temp;
                    temp = w[i];
                    w[i] = w[j];
                    w[j] = temp;
                }
        }//将物品按照单位重量价值排序；
    }
    int bound(int t)
    {
        int cleft = C - CurWeight;//剩余容量
        int b = CurValue;//现阶段背包内物品的价值
        while (t <= n && w[t] <= cleft)//以物品重量价值递减装入物品
        {
            cleft = cleft - w[t];
            b = b + v[t];
            t++;
        }
        if (t <= n)//装满背包
            b = b + v[t] * cleft / w[t];//计算t号物品的单位价值装满剩余空间
        return b;
    }
    void backtrack(int t)
    {
        if (t > n)//到达叶子节点了
        {
            if (CurValue > BestValue)//已经搜寻完一次了，把现有的最大值赋值；
            {
                BestValue = CurValue;
                for (int i = 1; i <= n; i++)
                    BestX[i] = X[i];
            }
            return;
        }
        if (CurWeight + w[t] <= C)//不到背包最大容量进入左子树
        {
            X[t] = 1;//记录是否装入
            CurWeight += w[t];
            CurValue += v[t];
            backtrack(t + 1);//回溯
            CurWeight -= w[t];
            CurValue -= v[t];
        }
        if (bound(t + 1) > BestValue)//进入右子树
        {
            X[t] = 0;//他自己没有后面物品合适
            backtrack(t + 1);//判断
        }
    }
    int main()
    {
        cin >> C >> n; //背包容量和物品个数
        for (int i = 1; i <= n; i++)//都是从一开始的
        {
            cin >> w[i]; //物品重量
            order[i] = i;//序列号的意思
        }
        for (int i = 1; i <= n; i++)
            cin >> v[i];//物品价值
        knapsack();
        backtrack(1);
        cout<<BestValue<<endl;
        for (int i = 1; i <= n - 1; i++)
        {
            for (int j = 1; j <= n - 1; j++)
            {
                if (order[j] > order[j + 1])
                {
                    t = order[j];
                    order[j] = order[j + 1];
                    order[j + 1] = t;
                    t = BestX[j];
                    BestX[j] = BestX[j + 1];
                    BestX[j + 1] = t;
                }
            }
        }//他要求输出的是原来的序号
        for (int i = 1; i <= n; i++)
            cout<<BestX[i];
        return 0;
    }

#### 真回溯算法 ####

#include <stdio.h>
    #include <stdlib.h>
    #define N 100
    int n, c, maxValue = 0; // 物品数量，背包容量，最大价值
    int w[N], v[N]; // 物品重量，物品价值
    int path[N];
    int path0[N];
    void backtrack(int i, int res, int value) {
        if (i == n) {
            if (value > maxValue) {
                    maxValue = value;
                    for (int i = 0; i < n; i++) path0[i] = path[i];
            }
            return;
        }
        path[i] = 1;
        if (res >= w[i]) {
                backtrack(i + 1, res - w[i], value + v[i]); // 考虑第i个物品放入背包
        }
        path[i] = 0;
        backtrack(i + 1, res, value); // 不考虑第i个物品放入背包
    }
    
    int main() {
        scanf("%d%d", &n, &c);
        for (int i = 0; i < n; i++) scanf("%d%d", &w[i], &v[i]);
        backtrack(0, c, 0);
        printf("%d\n", maxValue);
        for (int i = 0; i < n; i++) printf("%d ", path0[i]);
        return 0;
    }

## 题目二**旅行售货员问题** ##

> 设有一个售货员从城市1出发，到城市2,3,..,n去推销货物，最后回到城市1。假定任意两个城市i，j间的距离dij(dij=dji)是已知的，问他应沿着什么样的路线走，才能使走过的路线最短。

#include <stdio.h>
    #include <stdbool.h>
    #define MAXN 100 // 最大城市数
     
    int n;             // 城市数
    int graph[MAXN][MAXN]; // 图的邻接矩阵
    int path[MAXN],bestPath[MAXN];    // 保存当前路径
    bool visited[MAXN]; // 标记城市是否访问过
    int minDist = 0x7fffffff; // 保存最短路径的长度
     
    void backtracking(int cur, int dist) {
        if (cur == n) {  // 所有城市都已经走过了
            if (dist + graph[path[n - 1]][0] < minDist) {
                minDist = dist + graph[path[n - 1]][0]; // 更新最短路径
                for(int i = 0;i < n;i++){
                    bestPath[i] = path[i];
                }
            }
            return;
        }
        for (int i = 1; i < n; i++) { // 枚举下一个城市
            if (!visited[i]) {        // 如果这个城市还没有访问过
                path[cur] = i;         // 选择这个城市
                visited[i] = true;     // 标记这个城市已经访问过
                backtracking(cur + 1, dist + graph[path[cur - 1]][i]); // 递归到下一层
                visited[i] = false;    // 回溯，撤销选择
            }
        }
    }
     
    int main() {
        scanf("%d", &n); // 输入城市数
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &graph[i][j]); // 输入邻接矩阵
            }
        }
        path[0] = 0;       // 起点是城市0
        visited[0] = true; // 标记起点已经访问过
        backtracking(1, 0); // 从第2个城市开始递归
        printf("%d\n", minDist); // 输出最短路径长度
        for(int i = 0;i < n;i++){
            printf("%d ",bestPath[i]+1);
        }
        return 0;
    }

[Link 1]: https://blog.csdn.net/qq_62377885/article/details/130272436