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