10个人排队买商品的最佳方案：C语言贪心算法实现

本文讨论了 10 个人排队购买一件价格为 5 元的商品的最佳方案。其中一半人持有 10 元人民币，另一半人持有 5 元人民币。为了避免售货员找零困难，我们需要找到一种合适的排队方式。

思路：

由于一半的人拿 10 元人民币，一半的人拿 5 元人民币，因此可以考虑将持有 10 元人民币的人放在队伍的前面，持有 5 元人民币的人放在队伍的后面。这样，在售货员开始售货时，前面的人会先使用 10 元人民币进行支付，售货员可以用 5 元人民币找零给后面的人，不会出现找零困难的情况。

所有排队方案：

10 10 10 10 10 5 5 5 5 5
10 10 10 10 5 10 5 5 5 5
10 10 10 5 10 10 5 5 5 5
10 10 5 10 10 10 5 5 5 5
10 5 10 10 10 10 5 5 5 5
5 10 10 10 10 10 5 5 5 5
10 10 10 10 5 5 10 5 5 5
10 10 10 5 10 5 10 5 5 5
10 10 5 10 5 10 10 5 5 5
10 5 10 5 10 10 10 5 5 5
5 10 5 10 10 10 10 5 5 5
10 10 10 5 5 10 10 5 5 5
10 10 5 10 5 10 5 10 5 5
10 5 10 5 10 5 10 10 5 5
5 10 5 10 5 10 10 10 5 5
10 10 5 5 10 10 10 5 5 5
10 5 10 5 10 10 5 10 5 5
5 10 5 10 10 5 10 10 5 5
10 5 5 10 10 10 10 10 5 5
5 10 5 5 10 10 10 10 5 5
10 5 5 10 5 10 10 10 5 5
5 10 5 5 10 5 10 10 5 5
5 5 10 10 10 10 10 10 5 5
5 10 5 5 5 10 10 10 10 5
5 5 10 5 10 10 10 10 10 5
5 5 5 10 10 10 10 10 10 5
10 5 5 5 10 10 10 10 10 5
5 10 5 5 5 5 10 10 10 10
5 5 10 5 5 10 10 10 10 10
5 5 5 10 5 10 10 10 10 10
5 5 5 5 10 10 10 10 10 10

C语言贪心算法实现：

#include <stdio.h>

int main()
{
    int people[10] = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1}; // 0表示持有10元人民币，1表示持有5元人民币
    int i, j, temp, count = 1;
    printf("所有排队方案如下：\n");
    do
    {
        printf("%d. ", count++);
        for (i = 0; i < 10; i++) // 冒泡排序
        {
            for (j = i + 1; j < 10; j++)
            {
                if (people[i] > people[j])
                {
                    temp = people[i];
                    people[i] = people[j];
                    people[j] = temp;
                }
            }
            printf("%d ", people[i] == 0 ? 10 : 5);
        }
        printf("\n");
    } while (next_permutation(people, people + 10)); // 使用STL库函数生成下一个排列
    return 0;
}

代码说明：

people 数组用于存储每个人持有的货币类型，0 代表 10 元，1 代表 5 元。
next_permutation() 函数用于生成数组的下一个排列，从而生成所有可能的排队方案。
代码通过循环遍历所有可能的排列，并输出每个排列对应的排队方案。

结论：

本文通过分析和 C 语言实现，找到了 10 个人排队购买 5 元商品的最佳方案，即所有持有 10 元人民币的人排在前面，所有持有 5 元人民币的人排在后面。这样可以有效地避免售货员找零困难。