• 回溯法解排队购物问题(C++)


    一、问题描述

    2n 个人排队购买一件价格为 0.5 元的商品,其中一半人拿一张 1 元人民币,另一半人拿一张 0.5 元的人民币。售货员在开始时没有准备零钱,要求找出所有排队的方案,使得售货员在售货中不发生找零困难。


    二、题解

    #include 
    #include 
    
    using namespace std;
    
    class Solution
    {
    private:
        vector<vector<int>> result;  // 结果集
        int five_count = 0;  // 队列中拿着0.5元的人数计数器
        int one_count = 0;  // 队列中拿着1元的人数计数器
    
    public:
        vector<vector<int>> queueShop(int n) {
            vector<int> each_case;
    
            backtracking(each_case, n);
            
            return result;
        }
    
        void backtracking(vector<int> &each_case, int n) {
            if (each_case.size() == 2 * n) {
                result.emplace_back(each_case);
                return;
            }
    
    		/* 只要0.5的数目没达到一半,就继续添加0.5 */
            if (five_count < n) {
                each_case.emplace_back(5);
                five_count++;
                backtracking(each_case, n);
                each_case.pop_back();
                five_count--;
            }
    
            /* 只有当前队列中0.5的数目多于1时才考虑加入1 */
            if (one_count < n && five_count > one_count) {
                each_case.emplace_back(1);
                one_count++;
                backtracking(each_case, n);
                each_case.pop_back();
                one_count--;
            }
        }
    };
    
    int main(int argc, char *argv[]) {
        Solution solution;
    
        auto res = solution.queueShop(5);
    
        for (const auto &i : res) {
            for (const auto &j : i) {
                cout << j << " ";
            }
            cout << endl;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59

    三、运行结果

    atreus@MacBook-Pro % clang++ main.cpp -o main -std=c++11
    atreus@MacBook-Pro % ./main                             
    5 5 5 5 5 1 1 1 1 1 
    5 5 5 5 1 5 1 1 1 1 
    5 5 5 5 1 1 5 1 1 1 
    5 5 5 5 1 1 1 5 1 1 
    5 5 5 5 1 1 1 1 5 1 
    5 5 5 1 5 5 1 1 1 1 
    5 5 5 1 5 1 5 1 1 1 
    5 5 5 1 5 1 1 5 1 1 
    5 5 5 1 5 1 1 1 5 1 
    5 5 5 1 1 5 5 1 1 1 
    5 5 5 1 1 5 1 5 1 1 
    5 5 5 1 1 5 1 1 5 1 
    5 5 5 1 1 1 5 5 1 1 
    5 5 5 1 1 1 5 1 5 1 
    5 5 1 5 5 5 1 1 1 1 
    5 5 1 5 5 1 5 1 1 1 
    5 5 1 5 5 1 1 5 1 1 
    5 5 1 5 5 1 1 1 5 1 
    5 5 1 5 1 5 5 1 1 1 
    5 5 1 5 1 5 1 5 1 1 
    5 5 1 5 1 5 1 1 5 1 
    5 5 1 5 1 1 5 5 1 1 
    5 5 1 5 1 1 5 1 5 1 
    5 5 1 1 5 5 5 1 1 1 
    5 5 1 1 5 5 1 5 1 1 
    5 5 1 1 5 5 1 1 5 1 
    5 5 1 1 5 1 5 5 1 1 
    5 5 1 1 5 1 5 1 5 1 
    5 1 5 5 5 5 1 1 1 1 
    5 1 5 5 5 1 5 1 1 1 
    5 1 5 5 5 1 1 5 1 1 
    5 1 5 5 5 1 1 1 5 1 
    5 1 5 5 1 5 5 1 1 1 
    5 1 5 5 1 5 1 5 1 1 
    5 1 5 5 1 5 1 1 5 1 
    5 1 5 5 1 1 5 5 1 1 
    5 1 5 5 1 1 5 1 5 1 
    5 1 5 1 5 5 5 1 1 1 
    5 1 5 1 5 5 1 5 1 1 
    5 1 5 1 5 5 1 1 5 1 
    5 1 5 1 5 1 5 5 1 1 
    5 1 5 1 5 1 5 1 5 1 
    atreus@MacBook-Pro % 
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    在这里插入图片描述

  • 相关阅读:
    含文档+PPT+源码等]精品基于NET实现的司库管理系统-金融理财管理系统[包运行成功]
    安卓学习路线参考
    SpringSecurity入门和项目中使用
    verilog-延迟语句
    [2023毕业设计源码]精品基于PHP实现的剧影评|剧评影评系统[包运行成功]
    《DREEAM Guiding Attention with Evidence for Improving Document-Level Relation Extraction》阅读笔记
    Python自然语言处理库之textblob使用详解
    日期类的实现
    【AI】Python 实现 KNN 手写数字识别
    LeetCode:9. 回文数
  • 原文地址:https://blog.csdn.net/qq_43686863/article/details/127787870