Counting problem C#

Question

I've a bit of a problem. I'm adding numbers to ArrayList like 156, 340 (when it is TransferIn or Buy) etc and then i remove them doing it like 156, 340 (when it's TransferOut, Sell). Following solution works for that without a problem. The problem I have is that for some old data employees were entering sum's like 1500 instead of 500+400+100+500. How would I change it so that when there's Sell/TransferOut and there's no match inside ArrayList it should try to add multiple items from that ArrayList and find elements that combine into aggregate.

   ArrayList alNew = new ArrayList();
   ArrayList alNewPoIle = new ArrayList();
   ArrayList alNewCo = new ArrayList();
   string tempAkcjeCzynnosc = (string) alInstrumentCzynnoscBezNumerow[i];
   string tempAkcjeInId = (string) alInstrumentNazwaBezNumerow[i];
   decimal varAkcjeCena = (decimal) alInstrumentCenaBezNumerow[i];
   decimal varAkcjeIlosc = (decimal) alInstrumentIloscBezNumerow[i];
   int index;
   switch (tempAkcjeCzynnosc) {                  

          case "Sell":
          case "TransferOut":
          index = alNew.IndexOf(varAkcjeIlosc);
          if (index != -1) {
              alNew.RemoveAt(index);
              alNewPoIle.RemoveAt(index);
              alNewCo.RemoveAt(index);
          } else {
              // Number without match encountred
          }
          break;

          case "Buy":
          case "TransferIn":
               alNew.Add(varAkcjeIlosc);
               alNewPoIle.Add(varAkcjeCena);
               alNewCo.Add(tempAkcjeInId);
               break;
    }
}

When you hit that special case.... sort the array and start summing the elements until you hit/pass the value (1500 in your example). If you hit it then you got a combination that you can transfer out, if not .. there is no such combination, move on ... :) — tzup, Mar 19 '10 at 10:26
@tzup - not true. Consider the elements `1 12 100` and the value `101`. You would sum `1 + 12 = 13` and then `100 + 13 = 113` and say there is no solution, when in fact there is. — IVlad, Mar 19 '10 at 10:33
you're right, I guess I was typing a lot faster than I was thinking. — tzup, Mar 19 '10 at 11:11

score 4 · Answer 1 · answered Mar 19 '10 at 10:19

4

This could prove trickier than you might think:

answered Mar 19 '10 at 10:19

LukeH

263,068
57
365
409

Well I have to somehow solve this as this added up in database. I could do it SUM and do CASE WHEN in there but problem it doesn't tell me which packets are kicked out and which are still in. We will be cleaning this mess when database goes live but until then I have to have working solution so that "results" are the one i expect it too. Later on i will delete 1500 and insert 5 Sell/TransferOut packets to resolve this. But this will be hand job so gonna take a while. – MadBoy Mar 19 '10 at 10:24
The list will vary. sometimes 30 items, sometimes less. sometimes more. Depending on how long we have him as customer. – MadBoy Mar 19 '10 at 10:33
Well I hope this will be temporary solution as I will be pushing employees to actually remove sums and put proper values in it's place, but until they do that i have to get counting right. – MadBoy Mar 19 '10 at 10:38
DP will work very fast for a few hundred elements. Assuming the numbers aren't huge anyway (in the ten thousands should be fine). – IVlad Mar 19 '10 at 10:39
Take a look at IVlad's answer, and the links in that answer. That's probably your best bet in this case. – LukeH Mar 19 '10 at 10:40

score 3 · Accepted Answer · edited May 23 '17 at 12:07

3

This is a variation of the knapsack problem called the subset sum problem. Check my answer here for multiple solutions. To get the actual items you need to remove if you use the dynamic programming approach, just keep a second array that tells you what was the last element you added to get a certain sum, then you can use that to find the solution. Post back if you can't get it working. If you have a lot of numbers, I suggest the randomized algorithm anyway, it is both easier to implement and more memory and time-efficient (usually).

edited May 23 '17 at 12:07

Community

1
1

answered Mar 19 '10 at 10:31

IVlad

43,099
13
111
179

Thanks, will try to work with it. Just had a talk with Director of department and he said they will those transactions before it will go live so hopefully there's no need for implementing this workaround. – MadBoy Mar 19 '10 at 10:56
IVlad if you're still so kind and can help me with subset sum problem please do. I've opened new question: http://stackoverflow.com/questions/2708436/subset-sum-problem – MadBoy Apr 25 '10 at 21:14

Counting problem C#

2 Answers2

Linked