計数問題 C#

Question

ちょっと問題があります。数字を追加しています ArrayList 156、340のような（それが TransferIn または Buy）など、それから私は156、340のようにそれを実行してそれらを削除します（それが TransferOut, Sell）。次の解決策は問題なく機能します。私が抱えている問題は、一部の古いデータについて、従業員が 500+400+100+500 ではなく 1500 のような合計を入力していたことです。Sell/TransferOut があり、ArrayList 内に一致がない場合に、その ArrayList から複数の項目を追加し、結合して集約される要素を検索するように変更するにはどうすればよいでしょうか。

   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

これは、ナップザック問題のバリエーションであり、 部分集合和問題. 。私の答えを確認してください ここ 複数のソリューションに対応します。動的プログラミングのアプローチを使用する場合に、削除する必要がある実際の項目を取得するには、特定の合計を取得するために追加した最後の要素を示す 2 番目の配列を保持しておき、それを使用して解を見つけることができます。うまく動作しない場合はポストバックしてください。数値が多い場合は、とにかくランダム化アルゴリズムをお勧めします。実装が簡単で、メモリと時間の効率も向上します (通常は)。

Answer 2

これはあなたが思っているよりも難しいことが判明する可能性があります。

• http://xkcd.com/287/
• http://en.wikipedia.org/wiki/ナップサック_問題