Recombination algorithm

Question

Imagine the following scenario: a gas station is fined for tax evasion for issuing tax coupons already issued - what happens is that each vehicle of the companies contracted to the station supplied and at the end of the month the post issued a tax note along with the respective invoice.

The operation, however, was done wrong for almost 2 years. There was no tax evasion under any circumstances, however, tax coupon numbers were not referenced to tax bills.

We are talking about an immense mass of data, where we basically need a match for amount of liters per fuel type x value - for example: a tax note of R $ 32.127,12 e 19.047,61 Liters of diesel oil has to be "regrouped" with N tax coupons.

However, we have the following problems: fuel prices vary, because the tax bill can be the combination of N pumps x N tax printers, that is, we are talking about a stratospheric mass of data.

However, knowing that we can limit the recombination "search" radius by date (last 30 days) - (which in data volume sums up to trillions of combinations in this period), could we use some tree algorithm? Or some variant algorithm of the traveling salesman?

Answer 1

Looks like you’re dealing with a backpack problem, in English Knapsack problem. It’s an NP-complete problem, so it doesn’t even have a quick fix, and performance only gets worse with increasing items. You mentioned that it’s a huge mass, so without much hope.

The advantage, in your case, is that tax coupons have date, and possibly time. Assuming the account closes, What you can do is sort these coupons by date and time, and back to front you add up all the items until you match or surpass the nearest date note. It equaled, it was lucky: take the coupons used, mark the note as ok, and start over. Failed the sum you "give up" the last coupon still alive, and repeat the process. This solution assumes that the system that issues orders does a similar process, taking only open coupons and closing in packets.

But the hypothesis that the account closes is actually very fragile. An alternative is to close sums of notes per day, for the days you "know for sure" on certain notes, and then you pick up the "uncertain" coupons on the previous or subsequent month’s note, depending on whether you have space on this or that.

Solution really, only you getting from the post(s) (s) that prepared that the relation of coupons and notes. Anything else, even the perfect knapsack solution of all coupons in all banknotes does not guarantee that this was the original relation. It’s just an approximation like any other in this indeterministic problem.