Knapsack Problem (Backpack Problem) SQL SERVER CTE RECURSIVE

Asked

Viewed 135 times

0

Good afternoon.

I am trying to develop a solution within the ERP of the company in which I work, with the objective of identifying the possibilities of INVOICES summed whose TOTAL is equal or approximate to an amount deposited in account.

If I select with a smaller TOTAL, I find the possibilities very quickly. When having do with a real situation, where the amount paid is much higher than that tested, select is running for hours with no result.

Could anyone suggest me another approach that is more efficient at runtime?

with
SomaFaturas (LastHANDLE, SEQ, SOMA) as 
(select HANDLE as LastHANDLE, ''+CAST(HANDLE AS nvarchar(MAX)) AS SEQ, 
CAST(VALOR AS real) AS SOMA
from k_testefaturas
UNION ALL
SELECT f.HANDLE AS LASTHANDLE, S.SEQ+'-'+CAST(HANDLE AS nvarchar(MAX)) AS SEQ, F.VALOR+S.SOMA AS SOMA
FROM k_testefaturas F
INNER JOIN SomaFaturas S
ON F.HANDLE > S.LASTHANDLE and F.VALOR+S.SOMA<74540.81+0.10)
SELECT SEQ, CAST(SOMA AS numeric(18,2)) AS SOMA FROM SomaFaturas
WHERE SOMA BETWEEN 74540.81-0.10 AND 74540.81+0.10
ORDER BY SEQ

The k_testefactura table contains 76 invoices of various values. It is duly indexed to improve performance.

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

Here an example of the same select, but with a smaller TOTAL to be found:

inserir a descrição da imagem aqui

  • Knapsack is so complicated that there are encryption algorithms based on it but it was thought.

  • @Mateusfernandes: Could you create in SQL Fiddle model with the structure and test data? This facilitates the testing of possible suggestions.

  • 1

    @Josédiz, I created in Fiddle: http://sqlfiddle.com/#! 18/9cd01/3

No answers

Browser other questions tagged

You are not signed in. Login or sign up in order to post.