0

I need to create a combination of sum of values closest to the target value. The combination needs to be of x numbers, where x is defined by the user. The algorithm will output the combination closest to a target value entered by the user. I also need to display the keys (values) that the algorithm returns.

Here is how I think the algorithm will work:

Target: 575

Values with corresponding keys:

150 [0] | 75 [1] | 123 [2] | 212 [3] | 23 [4] | 89 [5] | 20 [6]

77 [7] | 39 [8] | 16 [9] | 347 [10] | 512 [11] | 175 [12]

User wants Groups of: 5 values

The algorithm now runs combinations of sum of 5 values on the whole set and returns a sum of the values closest to the target value of 575.

Result

150 [0] + 212 [3] + 23 [4] + 77 [7] + 89 [5] = 551

Keys used were 0, 3, 4, 7, and 5.

を使用できますArrays#combination(n)が、キーを追跡することはできません。「キー」=>「int値」を格納するハッシュを思いつくことができましたが、ハッシュに格納された値を組み合わせる最適化されたアルゴリズムを思いつく方法がわかりません。

{0=>"150"}
{1=>"212"}
{2=>"23"}
{3=>"77"}
{4=>"89"}

PS これは宿題ではありません。これは、履歴書に記載し、面接で話し、自分のアイデアをコードに変換する方法を学ぶための個人的なプロジェクトです。

4

2 に答える 2

1

インデックスを追跡するためにcombination、配列自体ではなく、配列のインデックスに適用できます。

array = [150, 75, 212, 23, 89, 20, 77, 39, 16, 347, 512, 175]
target = 575
x = 5

closest_indice =
array
.each_index.to_a
.combination(x)
.min_by{|is| (array.values_at(*is).inject(:+) - target).abs}

ただし、答えはあなたが主張するものとは異なります。

closest_indice # => [0, 3, 7, 8, 9]
array.values_at(*closest_indice) # => [150, 23, 39, 16, 347]
array.values_at(*closest_indice).inject(:+) # => 575

なぜあなたが別の答えを持っているのか理解できません。

編集

私のステファンに気づいたように、インデックスはありません2。それに対処するには：

hash = {0 => 150, 1 => 75, 3 => 212, 4 => 23, 5 => 89, 6 => 20, 7 => 77, 8 => 39, 9 => 16, 10 => 347, 11 => 512, 12 => 175}
target = 575
x = 5

closest_keys =
hash
.keys
.combination(x)
.min_by{|is| (hash.values_at(*is).inject(:+) - target).abs}

closest_keys # => [0, 4, 8, 9, 10]
hash.values_at(*closest_indice) # => [150, 23, 39, 16, 347]
hash.values_at(*closest_indice).inject(:+) # => 575

この回答は、最初の質問に適用されます (つまり、OP が質問を変更し123て indexの要素を追加する前2)。

于 2013-09-20T07:12:42.833 に答える