Поиск комбинации хэшей для соответствия желаемому процентному распределению значений

Question

Учитывая массив хешей, я ищу способ выбрать случайное подмножество этих хешей, чтобы распределение атрибутов подмножества соответствовало желаемым процентам.

Например, для следующего массива:

[
  {
    question_id: 1,
    grade: 1,
    marks: [
      { topic: 'number', ao: 1 },
      { topic: 'ratios', ao: 2 }
    ]
  },
  {
    question_id: 2,
    grade: 3,
    marks: [
      { topic: 'number', ao: 2 },
      { topic: 'number', ao: 2 }
    ]
  },
  {
    question_id: 3,
    grade: 2,
    marks: [
      { topic: 'number', ao: 1 },
      { topic: 'geometry', ao: 1 },
      { topic: 'ratios', ao: 1 },
      { topic: 'number', ao: 2 },
      { topic: 'geometry', ao: 2 }
    ]
  },
  {
    question_id: 4,
    grade: 3,
    marks: [
      { topic: 'number', ao: 1 },
      { topic: 'ratios', ao: 2 },
      { topic: 'geometry', ao: 2 },
      { topic: 'geometry', ao: 2 }
    ]
  },
  {
    question_id: 5,
    grade: 1,
    marks: [
      { topic: 'ratios', ao: 1 },
      { topic: 'ratios', ao: 2 }
    ]
  },
  {
    question_id: 6,
    grade: 1,
    marks: [
      { topic: 'number', ao: 1 },
      { topic: 'number', ao: 2 },
      { topic: 'number', ao: 2 },
      { topic: 'ratios', ao: 2 }
    ]
  },
  {
    question_id: 7,
    grade: 3,
    marks: [
      { topic: 'number', ao: 2 }
    ]
  },
  {
    question_id: 8,
    grade: 3,
    marks: [
      { topic: 'geometry', ao: 1 }
    ]
  }
]

Я хотел бы найти случайную комбинацию, которая удовлетворяет следующему:

Общее количество марок = 10

50% оценок - номер темы
20% оценок - это тематические отношения
30% оценок - это геометрия темы

40% марок - 1
50% оценок - 2 класс
10% оценок - 3

50% марок - 1
50% марок - 2

Пример результата, который удовлетворяет этим требованиям:

[
  {
    question_id: 3,
    grade: 2,
    marks: [
      { topic: 'number', ao: 1 },
      { topic: 'geometry', ao: 1 },
      { topic: 'ratios', ao: 1 },
      { topic: 'number', ao: 2 },
      { topic: 'geometry', ao: 2 }
    ]
  },
  {
    question_id: 6,
    grade: 1,
    marks: [
      { topic: 'number', ao: 1 },
      { topic: 'number', ao: 2 },
      { topic: 'number', ao: 2 },
      { topic: 'ratios', ao: 2 }
    ]
  },
  {
    question_id: 8,
    grade: 3,
    marks: [
      { topic: 'geometry', ao: 1 }
    ]
  }
]

В идеале, если бы комбинация не существовала для удовлетворения этих требований (с некоторой степенью допуска), я ожидала бы получить ошибку.

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

Я начал с этого алгоритма, который находит все возможные комбинации чисел из массива для суммирования до желаемой суммы:

def subset_sum(numbers, target, partial=[], result=[])
    s = partial.inject 0, :+

    if s == target
      result << partial
    end

    return if s >= target

    (0..(numbers.length - 1)).each do |i|
      n = numbers[i]
      remaining = numbers.drop(i+1)
      subset_sum(remaining, target, partial + [n], result)
    end

    result
  end
end

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