Выбор группы элементов из массива, который удовлетворяет определенному условию

Question

Рассмотрим массив [1,2,3,4,3,2,4,1,2]. Я должен выбрать группу элементов (найти подмассива), общая сумма которых равна 5. После выбора группы эти элементы должны быть удалены из массива, пока не будет найдено сочетание элементов, удовлетворяющих условию. Для данного массива подмассивы будут [1,4] [2,3] [3,2] [4,1].

Мне нужны идеи о том, как написать оптимизированный алгоритм для этой проблемы.

Моя актуальная проблема имеет массив хэшей, как

[ 
    {name: 'name1', duration: 300.2, song_id: 1}, 
    {name: 'name2', duration: 412.7, song_id: 2} 
    ... 
] 

Я должен собрать массивы (группы) песен, так что их продолжительность лежит, например, в течение 29-30 минут или 9-10 минут. Длительность, указанная в примере хеша, находится в секундах.

Update:

Там нет Ограничить для числа элементов в выбранных группах.

Вот еще один пример, чтобы лучше понять проблему. Данный массив равен [10,20,30,40,50,5,15,25,35,45,55]. Мне нужно выбрать группы, общее количество которых составляет 50. Ответы будут [10,20,5,15],[50]

Answer 1

если заказ не имеет значения (я имею в виду ([4,1] == [4,1])) I имеют лучшее решение для компрометации.

Это алгоритм bruteforcing

def bruteforcing(arr) 
    arr.combination(2).find_all{ |x, y| x + y == 5 }.uniq 
end 

Это лучшее решение (I'ts только пример вы могли бы улучшить). Основная идея состоит в том, чтобы заказать массив и поиск пары противоположными крайностями в первом, и остановить поиск, если сумма значений мэра чем 5.

def search(arr) 
     ret=[] 
     arr.sort! 

     while arr != [] 
     current = arr.pop 
     arr.each.with_index do |value, index| 
      if current + value == 5 
      ret << [value,current] 
      arr.delete_at(index) 
      break 
      elsif current+value > 5 
      break 
      end 
     end 
     end 
     ret 
    end 

This is my search.rb (with benchmark) 

require "benchmark" 

def bruteforcing(arr) 
    arr.combination(2).find_all{ |x, y| x + y == 5 }.uniq 
end 

def search(arr) 
    ret=[] 
    arr.sort! 

    while arr != [] 
    current = arr.pop 
    arr.each.with_index do |value, index| 
     if current + value == 5 
     ret << [value,current] 
     arr.delete_at(index) 
     break 
     elsif current+value > 5 
     break 
     end 
    end 
    end 
    ret 
end 

def bench_times(n) 
    Benchmark.bm do |x| 
    puts "behc n times #{n}." 
    x.report { n.times{bruteforcing([1,2,3,4,3,2,4,1,2]) } } 
    x.report { n.times{ search([1,2,3,4,3,2,4,1,2]) } } 
    end 
end 

def bench_elements(n) 
    puts "bench with #{n} elements." 
    Benchmark.bm do |x| 
    a=[] 
    1_000.times { a<<rand(1..4) } 
    x.report { bruteforcing(a) } 
    a=[] 
    1_000.times { a << rand(1..4) } 
    x.report { search(a) } 
    end 
end 

puts bruteforcing([1,2,3,4,3,2,4,1,2]).to_s 
puts search([1,2,3,4,3,2,4,1,2]).to_s 

bench_times 1 
bench_times 5 
bench_times 1_000 
bench_times 1_000_000 

bench_elements(100) 
bench_elements(1_000) 
bench_elements(100_000) 
bench_elements(1_000_000) 

Выход:

[[1, 4], [2, 3], [3, 2], [4, 1]] 
[[1, 4], [1, 4], [2, 3], [2, 3]] 
     user  system  total  real 
behc n times 1. 
    0.000000 0.000000 0.000000 ( 0.000036) 
    0.000000 0.000000 0.000000 ( 0.000013) 
     user  system  total  real 
behc n times 5. 
    0.000000 0.000000 0.000000 ( 0.000118) 
    0.000000 0.000000 0.000000 ( 0.000037) 
     user  system  total  real 
behc n times 1000. 
    0.020000 0.000000 0.020000 ( 0.017804) 
    0.010000 0.000000 0.010000 ( 0.006673) 
     user  system  total  real 
behc n times 1000000. 
    16.580000 0.020000 16.600000 (16.583692) 
    5.970000 0.000000 5.970000 ( 5.968241) 
bench with 100 elements. 
     user  system  total  real 
    0.210000 0.010000 0.220000 ( 0.213506) 
    0.000000 0.000000 0.000000 ( 0.000863) 
bench with 1000 elements. 
     user  system  total  real 
    0.210000 0.000000 0.210000 ( 0.212349) 
    0.000000 0.000000 0.000000 ( 0.001539) 
bench with 100000 elements. 
     user  system  total  real 
    0.200000 0.000000 0.200000 ( 0.201456) 
    0.000000 0.000000 0.000000 ( 0.001067) 
bench with 1000000 elements. 
     user  system  total  real 
    0.190000 0.010000 0.200000 ( 0.199400) 
    0.010000 0.000000 0.010000 ( 0.000801)