arrays - 从满足特定条件的数组中选择一组元素

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 分钟之内。示例哈希中指定的持续时间以秒为单位。

更新:

所选组中的元素数量没有限制。

这里是另一个例子，可以更好地理解这个问题。给定数组是 [10,20,30,40,50,5,15,25,35,45,55]，我必须选择总数为 50 的组。答案将是 [10,20,5,15],[50]

Answer 1

如果顺序无关紧要(我的意思是 ([4,1]==[4,1]))，我有一个更好的暴力组合解决方案。

这是一个暴力破解算法

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

这是一个更好的解决方案(我只是一个您可以改进的示例)。主要思想是先按相反的极值对数组和搜索对进行排序，如果值之和大于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)