回溯法解排队购物问题（C++）

<>一、问题描述

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

<>二、题解
#include <iostream> #include <vector> 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; } }
<>三、运行结果
atreus@MacBook-Pro % clang++ main.cpp -o main -std=c++11 atreus@MacBook-Pro %
./main5 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 %

• « 上一篇：【Collection集合】概述、使用以及常用方法
• » 下一篇：电力行业智能电网建设背景