ansaurus

Question

Any set of rows that add up to target number

Answer 1

A:

try this:

Select * from sales where custid = 1 group by custid having sum(billamt) = 75

Vitaliy 2009-10-23 16:05:43

No, that will give no results (the only candidate row having a SUM(BillAmt) value of $100.00 in the case of the sample data).

Larry Lustig 2009-10-23 16:35:41

Answer 2

+4 A:

That's a variation of the knapsack problem, and you aren't going to solve it in SQL without a lot of procedural code. For starters, you're going to need recursion, and most SQL stored procedures don't cope at all well with recursion.

Craig Trader 2009-10-23 16:07:07

It seems to me to be a somewhat simplified version of that problem but yes, it's in the same domain. To make matters worse the programming language that goes with this database doesn't allow recursion at the application level, either.

Larry Lustig 2009-10-23 16:34:48

Thanks. I will (most likely) require the user to allocate the partial payment themselves or (less likely) write a small DLL in Delphi to solve the problem recursively.

Larry Lustig 2009-10-23 17:07:24

You can beat the recursion restriction by using arrays to fake a stack context, and lots of loops, but it ain't pretty. You could also do the same thing with temporary tables, but driving cursors through temporary tables that are being updated on the fly is non-trivial.

Craig Trader 2009-10-23 17:09:05

Have you considered telling the client that the correct answer is NOT to try to pay off individual items, but instead to just do what every other retail POS system does, and pay off complete orders? That's easy (and doesn't require recursion). If they insist on this 'feature' then I'd write them a separate estimate with very frightening prices.

Craig Trader 2009-10-23 17:09:40

@W that is not a possible or correct solution in this instance. In the actual application (which involves insurance, not clothing), there are two paying entities. When the "first payer", who receives only the total amount due, forwards only a partial payment a second bill must be created for the ultimate consumer. That bill, unlike the first, must be itemized. Given the nature of the application I'm convinced that that's correct and, to change it, numerous state and local government would have to update their accounting systems.

Larry Lustig 2009-10-23 17:15:30

Ah. My boss has a stack of bumper stickers that apply in this situation: "Creating the Legacy Systems of Tomorrow".In your situation, I'd suggest prorating the partial payment across the entire bill, such that if $75 was paid against $100, each item would get a partial payment (respectively) of $37.50, $15, $15, $3.75, and $3.75, since that's really what is happening. Even easier to implement.

Craig Trader 2009-10-23 17:49:59

At a co. I once worked at, we were working on crossing algorithms. The challenge was to find M buyers and N sellers in a brokerage network and match the sum of shares and the sale prices. This problem is like the subset sum problem. I researched the problem extensively. IT IS NOT EASY TO SOLVE.

Paul Chernoch 2009-10-23 19:24:02

Answer 3

A:

Because of the complexity (this pretty much is the knapsack problem that W. Craig Trader stated), I would recommend adding a PaidAmt column that you update based on a priority you define.

From your example, where the customer paid $75.00 and assuming the most expensive item is paid off first:

BillItemID    CustID    BillDate    Item    BillAmt  PaidAmt
1001          1         09-10-01    Suit    $50.00   $50.00
1002          1         09-10-01    Shirt   $20.00   $20.00
1003          1         09-10-01    Pants   $20.00   $5.00
1004          1         09-10-01    Tie      $5.00   $0.00
1005          1         09-01-10    Tie      $5.00   $0.00

After a little more digging, this is the Subset Sum problem and is NP-Complete. There is an "approximate" algorithm defined at the link.

Austin Salonen 2009-10-23 16:20:04

That's exactly WHY I need to find a set of rows that match the payment amount. I cannot simply start at the most expensive and pay them one by one because I want a set (if such exists) that will not result in a partial payment on any of the rows.

Larry Lustig 2009-10-23 16:32:48

What will you do when no set exists? How would tackle the customer paying $74.00?

Austin Salonen 2009-10-23 16:45:45

Then I will probably start at the "top" (as defined by the client), paying as I go and partial paying the last item I reach. According to the client this will "never" happen, but I'll have to code for it anyway. Nonetheless, right now I'm just interested in detecting and processing the case in which the payment can be exactly disbursed among a subset of the charges.

Larry Lustig 2009-10-23 17:01:20

Actually, I take that back. If the payment can't be exactly allocated I'll display a list of charges to the user and have them manually allocate the payment, checking to ensure they allocate the precise amount. I'll probably do this even if the payment does allocate exactly, but I'll be able to present them with an "already solved" solution in that case.

Larry Lustig 2009-10-23 17:03:52

I'd recommend paying in date order (oldest first) instead of by price -- presumably fees are charged for items unpaid for longer than 30/60/90 days...

Craig Trader 2009-10-23 17:11:19

@W in this application the payment received will only be applied to charges accrued on the same date. Any unpaid items will be "resolved" at the time the payment is applied through any one of a number of user selected resolution mechanisms.

Larry Lustig 2009-10-23 17:17:26

ansaurus

tags:

views:

answers:

Any set of rows that add up to target number

related questions