2

C# でこれを行う最善の方法を知りたいと思います。たとえば、20 個の数値の配列と、もう 1 つの追加の変数があります。指定された変数に最も近い数値の合計を取得したい。たとえば、1.1、1.5、1.7、1.9、2.2、3.1、3.2、1,5、4.5、4.1 があるとします。そして、追加の変数の値は 5 です。指定された数値に最も近い配列内のいくつかの数値の合計を取得したいのですが、その数値を取得したら、それらの数値をリストから削除して追加します新しい配列。すべてのコメントを歓迎します。ありがとう

4

1 に答える 1

4

サブセット和問題の最適化問題について説明しています。

問題はNP完全であるため、既知の多項式の解はありません。

ただし、入力はかなり小規模であるため、2 ^ 20〜= 1000000しかないため、すべてのサブセットをチェックする指数関数的なソリューションが実行可能です（実際にはもう少しですが、実行時間を見積もるには十分に近いです）

擬似コードは次のようになります。

getClosestSum(list,sum,number):
  if (list is empty):
      return sum
  candidate1 <- getClosest(list[1:],sum,number)
  candidate2 <- getClosest(list[1:],sum+list[0],number)
  if (abs(number-candidate1) < abs(number-candidate2)):
      return candidate1
  else:
      return candidate2
于 2012-11-29T20:31:36.657 に答える