C ++匹配数组中的双打（匹配中的条目数递增）

Question

美好的一天，

我是 C++ 的新手。我有一个项目，我需要提出一个应用程序来进行匹配。

假设共有 100 件商品，每件价格不同，存储在名为 PriceDB.txt.

的文本文件中

文本文件结构：

Item1 3.99
Item2 9.99
Item3 11.88
Item4 87.10
Item5 5.69
Item6 13.00
Item7 245.22
... (and so on)

它（应该）是这样工作的：

C++ 应用程序将请求输入您想匹配的价格
首先将 2 件商品的价格相加（商品 1 和商品 1），然后将总价与您输入的价格进行比较
如果 Item1 和 Item1 的价格总和与输入值不匹配，它将继续添加 Item1 和 Item2 的价格，然后 Item1 和 Item3 等等
如果直到Item1 & Item100 的总和仍不匹配，则继续添加Item2 & Item2、Item2 & Item3、Item2 & Item4 等等
注意上面只有2个价格组合。当到达 Item100 & Item100 仍未找到时，它继续 3 种价格组合..
例如Item1 & Item1 & Item1, Item1 & Item1 & Item2, 直到Item100 & Item100 & Item100, 继续4个价格组合
该过程将继续进行，直到达到 100 个价格组合。

我已经通过以下代码部分实现了我想要的：

#include <iostream>
#include <fstream>
#include <string>

using namespace std;


bool double_equals(double a, double b, double epsilon = 0.01)
{
    return abs(a - b) < epsilon;
}

int main() {

    double PriceToMatch, ItemPrice[5];
    string ItemName[5];

    ifstream PriceDB("PriceDB.txt", ios::binary);

    if (!PriceDB.is_open()) {
        cout << "ERROR: Failed to read price database, exiting...";
        return 1;
    }

    for (int i = 0; !PriceDB.eof(); i++) {
        PriceDB >> ItemName[i];
        PriceDB >> ItemPrice[i];
    }

    cout << "Enter the price to match: ";
    cin >> PriceToMatch;


    for (int i = 0; i < 5; i++) {
        for (int x = i; x < 5; x++) {
            if (double_equals(ItemPrice[i] + ItemPrice[x], PriceToMatch) == true) {
                cout << "Found: " << ItemName[i] << " + " << ItemName[x] << endl;
            }
        }
    }

    for (int a = 0; a < 5; a++) {
        for (int b = a; b < 5; b++) {
            for (int c = b; c < 5; c++) {
                if (double_equals(ItemPrice[a] + ItemPrice[b] + ItemPrice[c], PriceToMatch) == true) {
                    cout << "Found: " << ItemName[a] << " + " << ItemName[b] << " + " << ItemName[c] << endl;
                }
            }
        }
    }

    return 0;
}

以上代码适用于 2 个价格组合和 3 个价格组合。

但是，我必须在组合中添加更多套 If/else 才能获得更多价格。这将是一个非常大的麻烦，因为它会导致很多页面的代码。知道如何解决这个问题吗？

Answer 1

你能澄清一下初始任务吗？从你的描述中我看到你的首要任务是找到一组最小的数字。这是你想要的吗？我只是假设您想尽快找到答案 :) 那么你可以做什么：

对数组进行排序（降序）
启动递归函数（如果你愿意，可以将其重写为循环形式）

函数可能如下所示：

bool FindPriceToMatchFromPos(int pos, int PriceToMatch)
{
    if (ItemPrice[pos] == PriceToMatch) // Found the answer
    {
        resultIndices.push_back(pos); 
        return true;
    }
    else if (ItemPrice[pos] < PriceToMatch && pos < ItemPrice.size() - 1)
    {
        int residue = PriceToMatch - ItemPrice[pos];
        for (int i = pos + 1; i < ItemPrice.size(); i++)
        {
            if (FindPriceToMatchFromPos(i, residue))
            {
                resultIndices.push_back(pos);
                return true;
            }
        }
    }
    return false;
}

而你主要是：

int main ()
{
// There will be your result indices (or you can store values instead)
vector<int> resultIndices; 

bool SolutionFound = false;
for (int CurrentPosition = 0; !SolutionFound && CurrentPosition < ItemPrice.size(); CurrentPosition++)
     SolutionFound = FindPriceToMatchFromPos(CurrentPosition,  PriceToMatch);
// Your results (if any) stored in "resultIndices"
}

提示：如果您的程序仅以 2 位小数精度运行，我建议将您的值乘以 100 并将它们存储为整数。这样你就不需要那个丑陋的比较功能了；） PS。对不起我的英语

有关您的问题的更多理论细节，您可以访问：Sum-subset with a fixed subset size

C ++匹配数组中的双打（匹配中的条目数递增）

C++ Matching Doubles in an Array (With incremental number of entries in matching)

c++

combinations

permutation