C++匹配数组中的 double (匹配中的条目数递增)

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

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

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

函数可能是这样的:

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 并将它们存储为整数。这样你就不需要那个丑陋的比较功能了；) 附言。对不起我的英语

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