Блог

Учитывая этот хэш:

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

Как я могу вернуть пару ключ-значение этого хэша, если и когда сумма его ключей будет меньше или равна максимальному значению, такому как 10 ?

Ожидаемый результат будет примерно таким:

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

потому что сумма этих ключей равна 10.

Я зациклился на этом уже несколько часов и не могу найти ничего, что привело бы к решению.

Краткие сведения

1. В первом разделе я привожу некоторый контекст и хорошо прокомментированный рабочий пример того, как решить определенную проблему с рюкзаком за считанные микросекунды, используя небольшую грубую силу и некоторые классы ядра Ruby.
2. Во втором разделе я проведу рефакторинг и расширю код, чтобы продемонстрировать преобразование решения knapsack в результат, аналогичный тому, что вы хотите, хотя (как объяснено и продемонстрировано в ответе ниже) правильный вывод при наличии нескольких результатов должен представлять собой набор хеш-объектов, а не один хеш, если существуют дополнительные критерии отбора, не включенные в ваш первоначальный пост.
3. Пожалуйста, обратите внимание, что в этом ответе используется синтаксис и классы из Ruby 3.0, и он был специально протестирован на Ruby 3.0.3. Хотя он должен работать на Ruby 2.7.3 без изменений, и с большинством поддерживаемых в настоящее время версий Ruby 2.x с небольшим рефакторингом, ваш пробег может отличаться.

Решение проблемы с рюкзаком с помощью методов Ruby Core

Похоже, это вариант проблемы с рюкзаком, когда вы пытаетесь оптимизировать заполнение контейнера заданного размера. На самом деле это сложная проблема, которая является NP-полной, поэтому в реальном приложении такого типа будет много разных решений и возможных алгоритмических подходов.

Я не утверждаю, что следующее решение является оптимальным или подходящим для решений общего назначения для этого класса проблем. Однако это работает очень быстро, учитывая предоставленные входные данные из вашего исходного сообщения.

Его пригодность в первую очередь основана на том факте, что у вас довольно небольшое количество хеш-ключей, а встроенные в Ruby 3.0.3 основные методы Hash#permutation и Enumerable#sum достаточно быстры, чтобы решить эту конкретную проблему где-то за 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
 

Возвращает массив совпадающих хэшей

Приведенный выше код просто возвращает список ключей, которые поместятся в ваш рюкзак, но в соответствии с вашим исходным сообщением вы хотите вернуть хэш совпадающих пар ключ / значение. Проблема здесь в том, что у вас на самом деле есть более одного набора хеш-объектов, которые будут соответствовать критериям, поэтому ваша коллекция должна фактически представлять собой массив, а не один хеш. Возврат только одного хэша в основном вернет исходный хэш за вычетом любых ключей, которые превышают ваше MAX_VALUE , и это вряд ли будет то, что задумано.

Вместо этого, теперь, когда у вас есть список ключей, которые помещаются в ваш рюкзак, вы можете выполнить итерацию по своему исходному хэшу и использовать Hash#select, чтобы вернуть массив уникальных хэш-объектов с соответствующими парами ключ / значение. Один из способов сделать это — использовать Enumerable#reduce для вызова Hash#merge для каждого хеш-элемента в подмассивах, чтобы преобразовать конечный результат в массив хеш-объектов. Затем вы должны вызвать 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 для конечного массива объектов Hash, это правильно даст 7 уникальных хэшей, которые соответствуют вашим определенным критериям, если не обязательно один хэш, который вы, кажется, ожидаете:

 [{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}]