Subset sum problem

Posted by MadBoy on Stack Overflow See other posts from Stack Overflow or by MadBoy
Published on 2010-04-25T13:50:31Z Indexed on 2010/04/25 13:53 UTC
Read the original article Hit count: 304

Filed under:
|
|

I'm having a problem with counting which is continuation of this question. I am not really a math person so it's really hard for me to figure out this subset sum problem which was suggested as resolution.

I'm having 4 ArrayList in which I hold data: alId, alTransaction, alNumber, alPrice

Type | Transaction | Number | Price
8 | Buy | 95.00000000 | 305.00000000
8 | Buy | 126.00000000 | 305.00000000
8 | Buy | 93.00000000 | 306.00000000
8 | Transfer out | 221.00000000 | 305.00000000
8 | Transfer in | 221.00000000 | 305.00000000
8 | Sell | 93.00000000 | 360.00000000
8 | Sell | 95.00000000 | 360.00000000
8 | Sell | 126.00000000 | 360.00000000
8 | Buy | 276.00000000 | 380.00000000

In the end I'm trying to get what's left for customer and what's left I put into 3 array lists: alNew (corresponds to alNumber), alNewPoIle (corresponds to alPrice), and alNewCo (corrseponds to alID)

        ArrayList alNew = new ArrayList();
        ArrayList alNewPoIle = new ArrayList();
        ArrayList alNewCo = new ArrayList();
        for (int i = 0; i < alTransaction.Count; i++) {
            string tempAkcjeCzynnosc = (string) alTransaction[i];
            string tempAkcjeInId = (string) alID[i];
            decimal varAkcjeCena = (decimal) alPrice[i];
            decimal varAkcjeIlosc = (decimal) alNumber[i];
            int index;
            switch (tempAkcjeCzynnosc) {
                case "Transfer out":
                case "Sell":
                    index = alNew.IndexOf(varAkcjeIlosc);
                    if (index != -1) {
                        alNew.RemoveAt(index);
                        alNewPoIle.RemoveAt(index);
                        alNewCo.RemoveAt(index);
                    } else {
                        ArrayList alTemp = new ArrayList();
                        decimal varAkcjeSuma = 0;
                          for (int j = 0; j < alNew.Count; j ++) {
                              string akcjeInId = (string) alNewCo[j];
                              decimal akcjeCena = (decimal) alNewPoIle[j];
                              decimal akcjeIlosc = (decimal) alNew[j];

                              if (tempAkcjeInId == akcjeInId && akcjeCena == varAkcjeCena) {
                                  alTemp.Add(j);
                                  varAkcjeSuma = varAkcjeSuma + akcjeIlosc;
                              }

                          }
                        if (varAkcjeSuma == varAkcjeIlosc) {
                            for (int j = alTemp.Count -1 ; j >=0 ; j --) {
                                int tempIndex = (int) alTemp[j];
                                  alNew.RemoveAt(tempIndex);
                                  alNewPoIle.RemoveAt(tempIndex);
                                  alNewCo.RemoveAt(tempIndex);
                            }
                        }
                    }
                    break;
                case "Transfer In":
                case "Buy":
                    alNew.Add(varAkcjeIlosc);
                    alNewPoIle.Add(varAkcjeCena);
                    alNewCo.Add(tempAkcjeInId);
                    break;

            }
        }

Basically I'm adding and removing things from Array depending on Transaction Type, Transaction ID and Numbers. 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). My 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 or Buy/Transfer In and there's no match inside ArrayList it should try to add multiple items from thatArrayList and find elements that combine into aggregate.

Inside my code I tried to resolve that problem with simple summing everything when there's no match (index == 1)

                    if (index != -1) {
                        alNew.RemoveAt(index);
                        alNewPoIle.RemoveAt(index);
                        alNewCo.RemoveAt(index);
                    } else {
                        ArrayList alTemp = new ArrayList();
                        decimal varAkcjeSuma = 0;
                          for (int j = 0; j < alNew.Count; j ++) {
                              string akcjeInId = (string) alNewCo[j];
                              decimal akcjeCena = (decimal) alNewPoIle[j];
                              decimal akcjeIlosc = (decimal) alNew[j];

                              if (tempAkcjeInId == akcjeInId && akcjeCena == varAkcjeCena) {
                                  alTemp.Add(j);
                                  varAkcjeSuma = varAkcjeSuma + akcjeIlosc;
                              }

                          }
                        if (varAkcjeSuma == varAkcjeIlosc) {
                            for (int j = alTemp.Count -1 ; j >=0 ; j --) {
                                int tempIndex = (int) alTemp[j];
                                  alNew.RemoveAt(tempIndex);
                                  alNewPoIle.RemoveAt(tempIndex);
                                  alNewCo.RemoveAt(tempIndex);
                            }
                        }

But it only works if certain conditions are met, and fails for the rest.

© Stack Overflow or respective owner

Related posts about c#

Related posts about .net-3.5