Problème de comptage C#

Question

J'ai un peu de problème. J'ajoute des nombres à ArrayList comme 156, 340 (quand c'est TransferIn ou Buy) etc. et puis je les enlève le faire comme 156, 340 (quand c'est TransferOut, Sell). La solution suivante fonctionne pour cela sans problème. Le problème que j'ai, c'est que pour certaines anciennes données, les employés saisissaient la somme comme 1500 au lieu de 500 + 400 + 100 + 500. Comment est-ce que je le changerais de sorte que quand il y a Sell/TransferOut et qu'il n'y ait aucune correspondance dans ArrayList il devrait essayer d'ajouter plusieurs éléments de cette ArrayList et trouver des éléments qui se combinent dans l'ensemble.

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

Ceci est une variante du problème de l'subset sum problem appelé havresac. Vérifiez ma réponse here pour plusieurs solutions. Pour obtenir les éléments réels que vous devez supprimer si vous utilisez l'approche de programmation dynamique, gardez juste un deuxième tableau qui vous indique quel était le dernier élément que vous avez ajouté pour obtenir une certaine somme, alors vous pouvez l'utiliser pour trouver la solution. Poster un message si vous ne pouvez pas le faire fonctionner. Si vous avez beaucoup de nombres, je suggère l'algorithme randomisé de toute façon, il est à la fois plus facile à implémenter et plus de mémoire et de temps (en général).

Answer 2

Cela pourrait se révéler plus délicat que vous pourriez penser:

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