吉利数红包算法

红包算法：

题目：

微信红包程序:

​ 给定一个钱数m ，发红包人数n，将钱数拆成尽可能多的吉利数，末尾带1，6，8的数（如0.01，0.06, 0.08，0.11，0.16, 0.18等)并发出(保证每人都有红包，吉利数尽可能多，大包和小包的概率都有，金额全部分完）,并去掉含 4 的吉利数。

分析：

因为要同时确保所有红包都分完，并且每个红包的金额尽可能是吉利数，这较难实现，需要更复杂的算法和逻辑。所以可以通过一种替代方法来实现：

可以只考虑个位数，因为吉利数只是末尾有{1，6，8}而对其他位数没有要求。可以先分配n个只有个位的吉利数，使这 n 个数相加的个位数等于 m 的个位数，这样 m 还会剩余一个没有个位的数，从而将这个数随机分配给数组中的数即可，因为它不会改变个位，也保证了还是吉利数。

步骤：

1. 使用回溯法，生成一个以 1、6、8 为组合的吉利数组，使得这个数组中的元素相加后的个位数之和等于 m 的个位数。
2. 将剩余的金额分配给各个红包。这个步骤采用随机分配的方式，确保每个红包金额在合理的范围内，并且不会影响其个位数。

回溯部分：

​ 此时的算法和经典组合问题相似，leetcode 216.组合总和III

本质就是找出相加之和的数 sum 与 m 的个位数相等，但是不能大于 m ； n 个数的组合，可选择的数组为 {1, 6, 8} 。

• 每个数字可以重复选择

回溯三部曲：

• 递归函数的返回值以及参数

    vector<vector<int>> res;            // 存放吉利数组集合
    vector<int> combination;            // 存放吉利数组

其实只要找到一个解就可以，但是为了随机可以创建一个集合，从中随机选择一个。

使用 sum 保存当前 combination 中的总和， m 为总数，n 为个数，start 为数组的起始位置（也是为了随机性）

void backtrack(int sum, int m, int n, int start)

• 递归终止条件

只有当 combination 中保存的数量等于 n，并且 数组和的尾数等于 m 的尾数时为找到了正确的解。

当 combination 中保存的数量 大于 n，或者 数组和的尾数不等于 m 的尾数 ,终止并回溯

• 单层搜索的逻辑

for (int digit : {1, 6, 8}) {
        // 当已经有一个吉利数组时，不再让重复
        if (digit == start && !res.empty()) {
            continue;
        }
        // 不能尾数大于 m
        if (sum + digit > m) {
            return;
        }
        combination.push_back(digit);               // 加入数组，进入回溯
        sum += digit;
        backtrack(sum, m, n, digit);
        if (res.size() == 5) {                      // 最多找到 5 个解即可
            return;
        }
        combination.pop_back();                     // 回溯
        sum -= digit;
}

完整代码：

// 分配吉利数红包的 个位
class Solution {
public:

    vector<vector<int>> res;            // 存放吉利数组集合
    vector<int> combination;            // 存放吉利数组

    // 数组和的尾数是否等于 m 的尾数
    bool isValid(int sum, int m) {
        return (sum % 10) == (m % 10);
    }

    // 回溯法生成吉利数组
    void backtrack(int sum, int m, int n, int start) {
        if (combination.size() == n) {              // 数组长度为 n 时
            if (isValid(sum, m)) {                  // 数组和的尾数等于 m 的尾数
                res.push_back(combination);         // 加入结果集
            }
            return;
        }
        if (combination.size() > n) {
            return;
        }
        for (int digit : {8, 1, 6}) {
            // 当已经有一个吉利数组时，不再让重复
            if (digit == start && !res.empty()) {
                continue;
            }
            // 不能尾数大于 m
            if (sum + digit > m) {
                continue;
            }
            combination.push_back(digit);               // 加入数组，进入回溯
            sum += digit;
            backtrack(sum, m, n, digit);
            if (res.size() == 5) {                      // 最多找到 5 个解即可
                return;
            }
            combination.pop_back();                     // 回溯
            sum -= digit;
        }
    }

    // 调用回溯法生成吉利数组
    vector<int> findCombination(int m, int n) {
        combination.clear();
        res.clear();
        backtrack(0, m, n, -1);
        // 随机返回一个吉利数组
        if (!res.empty()) {
            return res[rand() % res.size()];
        }
        return {};
    }
};

分配部分：

分配成功：

此时剩余的金额数量必是一个没有个位的数，但是因为 rand 函数的缺陷，所以可以可以将此时的 剩余金额 ÷ 10，在进行随机分配。

为了保证合理，每个红包的大小要控制在 二倍均值之内。（m * 2 / n)

需要以下变量：

    int remainSize;     // 剩余红包数量
    int remainMoney;    // 剩余红包金额
    vector<int> luckMoney; // 红包金额
    vector<int> money;  // 红包金额

其中 luckMoney 是回溯生成的吉利数组，money 是最后返回的红包数组

remainMoney 为剩余金额 ÷ 10

初始化：

remainSize = size;
Solution solution;
luckMoney = solution.findCombination(remainMoney, remainSize);
int m = remainMoney - accumulate(luckMoney.begin(), luckMoney.end(), 0);
remainMoney = m / 10;

判断是否有数字 4 :

通过转化成 string 判断

    bool containsFour(int num) {
        string str = to_string(num);
        if (str.find('4') != string::npos) {
            return true;
        }
        return false;
    }

分配金额：

distributeSingleMoney(int amount) 函数：

• 这个函数用于将一个指定金额的红包分配给剩余的吉利数数组中的某一个位置。
• 首先，通过 rand() % luckMoney.size() 随机选择一个位置，然后将指定金额加上该位置对应的吉利数添加到 money 数组中，并从 luckMoney 中删除该位置的吉利数。

    // 有解的情况下生成红包金额
    void distributeSingleMoney(int amount) {
        int index = rand() % luckMoney.size();
        money.push_back(amount * 10 + luckMoney[index]);
        luckMoney.erase(luckMoney.begin() + index);
    }

LastRedPackage() 函数：

• 这个函数用于处理最后一个红包金额包含数字 4 的情况。它尝试将最后一个红包金额拆分成两个不含数字 4 的红包。
• 首先，它遍历从 1 到 remainMoney - 1 的数，尝试找到一个数，使得剩余的红包金额不包含数字 4。
• 如果找到了这样的数，它将拆分后的两个金额分配给剩余的红包，并更新剩余金额和剩余红包数量。

 // 最后一个红包金额包含4 的情况下生成红包金额
    void LastRedPackage() {
        // 拆解成两个红包
        for (int i = 1; i < remainMoney; i++) {
            int num = remainMoney - i;
            // 如果拆解后的红包金额不含 4
            if (!containsFour(num)) {
                // 将拆解后的两个金额分配给剩余的红包
                for (int &j: money) {
                    // 如果拆解后的一个金额加上已有的金额不含 4
                    if (!containsFour(j + i * 10)) {
                        j += i * 10;
                        remainMoney -= i;
                        return;
                    }
                }
            }
        }
        // 如果拆解后的两个金额还是含 4, 不变
    }

getRandMoney() 函数：

• 这个函数是生成有解的情况下的红包金额的核心函数。
• 首先，它根据剩余金额的情况分为四种情况进行处理：
  • 如果剩余金额为 0，则将 randMoney 设为 0。
  • 如果剩余红包数量为 1，且剩余金额包含数字 4，则调用 LastRedPackage() 函数尝试拆分最后一个红包；否则将 randMoney 设为剩余金额。
  • 如果剩余金额小于剩余红包数量，则将 randMoney 设为 1。
  • 否则，根据剩余金额的两倍均值范围随机生成一个红包金额，并确保该金额不包含数字 4。
• 然后，根据 randMoney 更新剩余金额和剩余红包数量，并调用 distributeSingleMoney 函数将生成的红包金额分配给剩余的吉利数数组中的某一个位置。

通过这样的处理，getRandMoney 函数能够在有解的情况下，根据剩余金额和剩余红包数量，生成一个满足条件的红包金额列表。

	  void getRandMoney() {
        int randMoney = 0;
        if (remainMoney == 0) {
            randMoney = 0;
        } else if (remainSize == 1) {
            // 如果剩余一个红包并且 有 4
            if (containsFour(remainMoney)) {
                LastRedPackage();
                randMoney = remainMoney;
            } else {
                randMoney = remainMoney;
            }
        } else if (remainMoney < remainSize) {
            randMoney = 1;
        } else {
            int MaxMoney = remainMoney * 2 / remainSize;
            randMoney = rand() % MaxMoney;
            while (containsFour(randMoney)) {
                randMoney = rand() % MaxMoney;
            }
        }
        remainSize--;
        remainMoney -= randMoney;
        distributeSingleMoney(randMoney);
    }

分配失败：

在 n 或 m 数量较小时，可能会出现不能全部分配为吉利数的情况，此时需要特殊处理：

此时创建一个包含全部吉利数的数组然后随机选择即可，最后一个数直接为剩余金额。

吉利数组：

    for (int i = 1; i < remainMoney / remainSize * 2; i++) {
        if (containsFour(i)) {
            continue;
        }
        if (i % 10 == 1 || i % 10 == 6 || i % 10 == 8) {
            luckMoney.push_back(i);
        }
    }

分配金额：

    // 无解的情况下生成红包金额
    void getRandMoney2() {
        if (remainSize == 1) {
            money.push_back(remainMoney);
            remainSize--;
            return;
        }
        int MaxMoney = remainMoney * 2 / remainSize;
        int randMoney = getLucky2(MaxMoney);
        remainSize--;
        remainMoney -= randMoney;
        money.push_back(randMoney);
    }

    // 获取红包金额
    int getLucky2(int MaxMoney) {
        int index = 0;
        for (; index < luckMoney.size(); index++) {
            if (luckMoney[index] > MaxMoney) {
                break;
            }
        }
        int randIndex = rand() % index;
        return luckMoney[randIndex];
    }

不足：

• 金额分配不够随机
• 代码结构臃肿

源代码：

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <ctime>
#include <string>
using namespace std;

// 分配吉利数红包的 个位
class Solution {
public:

    vector<vector<int>> res;            // 存放吉利数组集合
    vector<int> combination;            // 存放吉利数组

    // 数组和的尾数是否等于 m 的尾数
    bool isValid(int sum, int m) {
        return (sum % 10) == (m % 10);
    }

    // 回溯法生成吉利数组
    void backtrack(int sum, int m, int n, int start) {
        if (combination.size() == n) {              // 数组长度为 n 时
            if (isValid(sum, m)) {                  // 数组和的尾数等于 m 的尾数
                res.push_back(combination);         // 加入结果集
            }
            return;
        }
        if (combination.size() > n) {
            return;
        }
        for (int digit : {8, 1, 6}) {
            // 当已经有一个吉利数组时，不再让重复
            if (digit == start && !res.empty()) {
                continue;
            }
            // 不能尾数大于 m
            if (sum + digit > m) {
                continue;
            }
            combination.push_back(digit);               // 加入数组，进入回溯
            sum += digit;
            backtrack(sum, m, n, digit);
            if (res.size() == 5) {                      // 最多找到 5 个解即可
                return;
            }
            combination.pop_back();                     // 回溯
            sum -= digit;
        }
    }

    // 调用回溯法生成吉利数组
    vector<int> findCombination(int m, int n) {
        combination.clear();
        res.clear();
        backtrack(0, m, n, -1);
        // 随机返回一个吉利数组
        if (!res.empty()) {
            return res[rand() % res.size()];
        }
        return {};
    }
};

//  分配吉利数红包的 其他位
class RedPackage {
public:

    int remainSize;     // 剩余红包数量
    int remainMoney;    // 剩余红包金额
    vector<int> luckMoney; // 红包金额
    vector<int> money;  // 红包金额
    bool isSolved = false;      // 是否有解

    RedPackage(int size, int money) {
        this->remainSize = size;
        this->remainMoney = money;
        getluckMoney();
    }

    // 生成吉利数红包数组    并且判断是否有解
    void getluckMoney() {
        Solution solution;
        luckMoney = solution.findCombination(remainMoney, remainSize);
        // 没有办法全部分配成吉利数
        if (luckMoney.empty()) {
            for (int i = 1; i < remainMoney / remainSize * 2; i++) {
                if (containsFour(i)) {
                    continue;
                }
                if (i % 10 == 1 || i % 10 == 6 || i % 10 == 8) {
                    luckMoney.push_back(i);
                }
            }
        }
        // 可以全部分配成吉利数
        else {
            int m = remainMoney - accumulate(luckMoney.begin(), luckMoney.end(), 0);
            remainMoney = m / 10;
            isSolved = true;
        }
    }

    // 判断是否有数字 4
    bool containsFour(int num) {
        string str = to_string(num);
        if (str.find('4') != string::npos) {
            return true;
        }
        return false;
    }

    // 有解的情况下生成红包金额
    void distributeSingleMoney(int amount) {
        int index = rand() % luckMoney.size();
        money.push_back(amount * 10 + luckMoney[index]);
        luckMoney.erase(luckMoney.begin() + index);
    }

    // 最后一个红包金额包含4 的情况下生成红包金额
    void LastRedPackage() {
        // 拆解成两个红包
        for (int i = 1; i < remainMoney; i++) {
            int num = remainMoney - i;
            // 如果拆解后的红包金额不含 4
            if (!containsFour(num)) {
                // 将拆解后的两个金额分配给剩余的红包
                for (int& j : money) {
                    // 如果拆解后的一个金额加上已有的金额不含 4
                    if (!containsFour(j + i * 10)) {
                        j += i * 10;
                        remainMoney -= i;
                        return;
                    }
                }
            }
        }
        // 如果拆解后的两个金额还是含 4, 不变
    }

    void getRandMoney() {
        int randMoney = 0;
        if (remainMoney == 0) {
            randMoney = 0;
        }
        else if (remainSize == 1) {
            // 如果剩余一个红包并且 有 4
            if (containsFour(remainMoney)) {
                LastRedPackage();
                randMoney = remainMoney;
            }
            else {
                randMoney = remainMoney;
            }
        }
        else if (remainMoney < remainSize) {
            randMoney = 1;
        }
        else {
            int MaxMoney = remainMoney * 2 / remainSize;
            randMoney = rand() % MaxMoney;
            while (containsFour(randMoney)) {
                randMoney = rand() % MaxMoney;
            }
        }
        remainSize--;
        remainMoney -= randMoney;
        distributeSingleMoney(randMoney);
    }

    // 无解的情况下生成红包金额
    void getRandMoney2() {
        if (remainSize == 1) {
            money.push_back(remainMoney);
            remainSize--;
            return;
        }
        int MaxMoney = remainMoney * 2 / remainSize;
        int randMoney = getLucky2(MaxMoney);
        remainSize--;
        remainMoney -= randMoney;
        money.push_back(randMoney);
    }

    // 获取红包金额
    int getLucky2(int MaxMoney) {
        int index = 0;
        for (; index < luckMoney.size(); index++) {
            if (luckMoney[index] > MaxMoney) {
                break;
            }
        }
        int randIndex = rand() % index;
        return luckMoney[randIndex];
    }

    // 分配红包
    vector<int> getRedPackage(int size) {
        if (isSolved) {
            for (int i = 0; i < size; i++) {
                getRandMoney();
            }
        }
        else {
            cout << "不能全部分配成吉利数红包" << endl;
            for (int i = 0; i < size; i++) {
                getRandMoney2();
            }
        }
        // 随机打乱红包顺序
        random_shuffle(money.begin(), money.end());
        return money;
    }

};

vector<double> getMoneyList(int m, int n) {
    vector<double> moneyList;
    RedPackage redPackage(n, m);
    vector<int> res = redPackage.getRedPackage(n);
    for (int i = 0; i < n; i++) {
        moneyList.push_back(double(res[i] / 100.0));
    }
    return moneyList;
}


int main() {
    srand((unsigned)time(NULL));
    double money = 0;
    int n = 0;
    while (true) {
        cout << "请输入红包金额和个数:" << endl;
        cin >> money >> n;
        if (money * 100 < n) {
            cout << "红包金额不能小于红包个数" << endl;
            continue;
        }
        break;
    }
    int m = money * 100;
    vector<double> moneyList = getMoneyList(m, n);
    double sum = 0;

    for (int i = 0; i < n; i++) {
        cout << "第" << i + 1 << "个红包是：" << moneyList[i] << " " << endl;
        sum += moneyList[i];
    }
    cout << "\nsum: " << sum << endl;

    return 0;
}