我如何 return 散列总和小于最大值的键对？

Question

给出这个哈希：

numsHash = {5=>10, 3=>9, 4=>7, 2=>5, 20=>4}

如果其键的总和小于或等于最大值（例如 10），我如何 return 此散列的键值对？

预期结果类似于：

newHash = { 5=>10, 3=>9, 2=>5 }

因为这些键的总和等于 10。

我已经为此困扰了几个小时，但找不到任何可以解决问题的方法。

Answer 1

总结

在第一部分中，我提供了一些背景知识和一个评论良好的工作示例，说明如何使用一点蛮力和一些 Ruby 核心 [=55] 在几微秒内解决定义的背包问题=]es.
在第二部分中，我重构并扩展了代码以演示如何将背包解决方案转换为与您想要的输出相似，尽管（如中所述和演示）下面的答案）当有多个结果时，正确的输出必须是哈希对象的集合而不是单个哈希，除非原始 post.
请注意，此答案使用 Ruby 3.0 中的语法和 classes，并专门针对 Ruby 3.0.3 进行了测试。虽然它应该在 Ruby 2.7.3+ 上工作而无需更改，并且对于大多数当前支持的 Ruby 2.x 版本有一些小的重构，你的里程可能会有所不同。

用Ruby核心方法解决背包问题

这似乎是 knapsack problem 的变体，您在其中尝试优化填充给定大小的容器。这实际上是一个复杂的 NP 完全问题，因此这种类型的实际应用将有许多不同的解决方案和可能的算法方法。

我并不声称以下解决方案是最佳解决方案或适用于此 class 问题的通用解决方案。但是，根据您提供的原始 post.

提供的输入数据，它的工作速度非常快

它的适用性主要是基于你的Hash key数量比较少，而且Hash#permutation and Enumerable#sum内置的Ruby3.0.3核心方法足够快来解决在我的特定机器上，这个特定问题在 44-189 微秒之间的任何地方。对于当前定义的问题来说，这似乎已经足够快了，但您的里程数和实际目标可能会有所不同。

# This is the size of your knapsack.
MAX_VALUE = 10

# It's unclear why you need a Hash or what you plan to do with the values of the
# Hash, but that's irrelevant to the problem. For now, just grab the keys.
#
# NB: You have to use hash rockets or the parser complains about using an
# Integer as a Symbol using the colon notation and raises SyntaxError.
nums_hash = {5 => 10, 3 => 9, 4 => 7, 2 => 5, 20 => 4}
keys = nums_hash.keys

# Any individual element above MAX_VALUE won't fit in the knapsack anyway, so
# discard it before permutation.
keys.reject! { _1 > MAX_VALUE }

# Brute force it by evaluating all possible permutations of your array, dropping
# elements from the end of each sub-array until all remaining elements fit.
keys.permutation.map do |permuted_array|
  loop { permuted_array.sum > MAX_VALUE ? permuted_array.pop : break }
  permuted_array
end

返回匹配哈希数组

上面的代码只是 return 适合你的背包的钥匙列表，但是根据你原来的 post 然后你想要 return 匹配的哈希 key/value 对。这里的问题是您实际上有不止一组符合条件的哈希对象，因此您的集合实际上应该是一个数组而不是单个哈希。仅返回单个哈希基本上 return 原始哈希减去任何超过您的 MAX_VALUE 的键，这不太可能是预期的。

相反，既然您有适合背包的钥匙列表，您可以遍历原始哈希并使用 Hash#select to return an Array of unique Hash objects with the appropriate key/value pairs. One way to do this is to use Enumerable#reduce to call Hash#merge on each Hash element in the subarrays to convert the final result to an Array of Hash objects. Next, you should call Enumerable#unique 删除除内部顺序之外的任何等效哈希。

例如，考虑这个重新设计的代码：

MAX_VALUE = 10

def possible_knapsack_contents hash
  hash.keys.reject! { _1 > MAX_VALUE }.permutation.map do |a|
    loop { a.sum > MAX_VALUE ? a.pop : break }; a
  end.sort
end

def matching_elements_from hash
  possible_knapsack_contents(hash).map do |subarray|
    subarray.map { |i| hash.select { |k, _| k == i } }.
      reduce({}) { _1.merge _2 }
  end.uniq
end

hash = {5 => 10, 3 => 9, 4 => 7, 2 => 5, 20 => 4}
matching_elements_from hash

给定定义的输入，如果不解决唯一性问题，这将产生 24 个哈希值。但是，通过在最终的哈希对象数组上调用#uniq，如果不一定是您似乎期望的单个哈希，这将正确地产生符合您定义的标准的 7 unique 哈希：

[{2=>5, 3=>9, 4=>7},
 {2=>5, 3=>9, 5=>10},
 {2=>5, 4=>7},
 {2=>5, 5=>10},
 {3=>9, 4=>7},
 {3=>9, 5=>10},
 {4=>7, 5=>10}]

我如何 return 散列总和小于最大值的键对？

How can I return hash pairs of keys that sum up to less than a maximum value?

ruby

hash

key

knapsack-problem

combinatorics

总结

用Ruby核心方法解决背包问题

返回匹配哈希数组