C ++递归：查找所有可能的具有不同价格的产品的购买组合

Question

假设我有 n 笔钱，物品 A 花费 1，物品 B 花费 2，物品 C 花费 3。

如何打印给定金额的所有可能的购买组合？

n=3 的输出应如下所示：C - A,B - B,A - A,A,A

遗憾的是，我提出的解决方案不起作用。

void purchase(int money)
{
    if (money == 0)
    {
        return;
    }
    else
    {
        if (money > 3)
        {
            cout << "C ";
            purchase(money - 3);
        }
        else if (money > 2)
        {
            cout << "B ";
            purchase(money - 2);
        }
        else if (money == 1)
        {
            cout << "A ";
        }
    }
}

Answer 1

使用支持缓冲区和缓冲区函数可以轻松实现此操作。这里str作为缓冲区，我把到现在遇到的字母保存在这里，而depth用来保持水平。

void purchase_impl(int money, char * str, int depth) {
    if (money == 0) {
        if (depth > 0) {
            str[depth] = '[=10=]';
            std::cout << str << std::endl;
        }
        return;
    }
    if (money >= 3) {
        str[depth] = 'C';
        purchase_impl(money-3, str, depth+1);
    }
    if (money >= 2) {
        str[depth] = 'B';
        purchase_impl(money-2, str, depth+1);
    }
    if (money >= 1) {
        str[depth] = 'A';
        purchase_impl(money-1, str, depth+1);
    }
}

void purchase(int money)
{
    char * str = (char *) malloc(money+1);
    purchase_impl(money, str, 0);
    free(str);
}

Answer 2

您需要跟踪您的路径，并测试正确的值并包括所有可能性。

void purchase(int money, string path = "")
{
    if (money == 0)
    {
        return;
    }
    if (money > 2)
    {
        string p = path + "C ";
        cout << p << "- ";
        purchase(money - 3, p);
    }
    if (money > 1)
    {
        string p = path + "B ";
        cout << p << "- ";
        purchase(money - 2, p);
    }
    string p = path + "A ";
    cout << p << "- ";
    purchase(money - 1, p);
}

此解决方案列出了所有可能的购买，包括不会耗尽您的现金供应的那些。

C ++递归：查找所有可能的具有不同价格的产品的购买组合

C++ recursion: Find all possible purchase-combinations of products with different prices

c++

recursion

subset-sum