Counting problem C#

Question

Hello,

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

Answer 1

This could prove trickier than you might think:

• http://xkcd.com/287/
• http://en.wikipedia.org/wiki/Knapsack_problem

Answer 2

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).