0

我需要创建最接近目标值的值的组合。组合必须是 x 个数字，其中 x 由用户定义。该算法将输出最接近用户输入的目标值的组合。我还需要显示算法返回的键（值）。

以下是我认为该算法的工作方式：

Target: 575

具有相应键的值：

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]

用户想要Groups of: 5 values

该算法现在在整个集合上运行 5 个值之和的组合，并返回最接近目标值的值之和575。

结果

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

使用的键是 0、3、4、7 和 5。

我可以使用Arrays#combination(n)，但我将无法跟踪密钥。我已经能够想出一个存储“key”=>“int values”的哈希，但我不知道如何想出一个优化的算法来组合存储在哈希中的值。

{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

我不明白为什么你有不同的答案。

编辑

正如我的 Stefan 所注意到的，没有 index 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 回答
1

像这样的东西会起作用：

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

# all key combinations of length 5
keys_of_5 = hash.keys.combination(5)
#=> #<Enumerator: [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12]:combination(5)>
#   i.e. [[0, 1, 2, 3, 4], [0, 1, 2, 3, 5], [0, 1, 2, 3, 6], ...]

# sum the values for each combination
sums_of_5 = keys_of_5.map { |keys| [keys, hash.values_at(*keys).inject(:+)] }
#=> [[[0, 1, 2, 3, 4], 583], [[0, 1, 2, 3, 5], 649], [[0, 1, 2, 3, 6], 580], ...]

# sort by distance to target
sorted = sums_of_5.sort_by { |keys, sum| (sum - 575).abs }
#=> [[[4, 5, 7, 8, 10], 575], [[0, 4, 8, 9, 10], 575], [[3, 4, 5, 7, 12], 576], ...]

# let's find the nearest ones
nearest = sorted.select { |keys, sum| sum == sorted.first[1] }

# and print 'em
nearest.each do |keys, sum|
  puts keys.map { |key| "%3d [%d]" % [hash[key], key] }.join(" + ") << " = #{sum}"
end

输出

 23 [4] +  89 [5] +  77 [7] +  39 [8] + 347 [10] = 575
150 [0] +  23 [4] +  39 [8] +  16 [9] + 347 [10] = 575
于 2013-09-20T07:24:08.050 回答