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

Question

Good day,

I'm fairly new to C++. I have a project that i need to come up with an application to do matching.

Let's say there are a total of 100 items, each with different prices, stored in a text file called PriceDB.txt.

The structure of text file:

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

Here's how it (should) works:

• The c++ application will request for input of what price would you like to match
• Starting with adding 2 items' prices together (Item1 & Item1), it compares the total with your input
• If the total of Item1 & Item1 price does not match the input value, it goes on adding Item1 & Item2's price, then Item1 & Item3 and so on
• If the total still doesn't match until the combination of Item1 & Item100, it goes on adding Item2 & Item2, Item2 & Item3, Item2 & Item4 and so on
• Note that the above only has 2 prices combination. When it reaches Item100 & Item100 and still not found, it continues with 3 prices combination..
• E.g. Item1 & Item1 & Item1, Item1 & Item1 & Item2, until Item100 & Item100 & Item100, it continues with 4 prices combination
• The process will go on until it reaches 100 prices combination.

I have partially achieved what i wanted with the codes below:

#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;
}

The codes above works for 2 prices combination and 3 prices combination.

However, I have to add more sets of If/else for more prices within a combination. This will be a really big hassle as it will result in lots of pages of codes. Any idea how to solve this problem?

Answer 1

Can you clarify initial task? From your description I see that your first priority is to find a minimum set of numbers. Is it what you want? I just presume that you want to find an answer as fast as possible :) So there what you can do:

1. Sort the array (in descending order)
2. Launch recursive function (you can rewrite it to cycle form if you wish)

Function could be look like this:

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;
}

And you main:

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"
}

Tip: If your program operates only with 2 decimal digits precision, I'd recomend to multiply your values by 100 and store them as integers. So that you won't need that ugly compare function ;) PS. Sorry for my English

For more theoretical details on your problem you can visit: Sum-subset with a fixed subset size