查找哈希组合以匹配所需的值百分比分布

问：

给定一个哈希数组，我正在寻找一种方法来选择这些哈希的随机子集，以便子集的属性分布与所需的百分比相匹配。

例如，给定以下数组：

[
  {
    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% 的分数是 AO 1
50% 的分数是 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: 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。对于这些数字，此解决方案的优化程度太低，并且运行时间很长。