php - 最有效的备案

现在的情况是，我必须用x个人数来填满房间。
对于本示例，我们可以使用：

$persons = 7;

我得到了一个数组：

$differentRoom = array(
    'Room 1' => 1, //This room fits 1 person
    'Room 2' => 2, //This room fits 2 persons
    'Room 3' => 3, //This room fits 3 persons
);

现在我希望php以最短的方式生成正好是7的组合。结果必须是，你需要：'Room3''Room3''Room1'
在另一个例子中

$persons = 15;

和一个数组

$differentRooms = array(
    'Room 1' => 4, // This room fits x persons
    'Room 2' => 7,
);

这次的组合不可能是15。
在这种情况下，结果必须是大于15的组合。
在这种情况下是16。16是最接近10的，结果必须是。你需要：“2号房间”“2号房间”“1号房间”
我该怎么做？

最佳答案

你需要贪婪的算法。这个应该有用。我已经写了

$differentRoom = array(
'Room 1' => 4,
'Room 2' => 7
);

$persons = 15;
arsort($differentRoom);

$min_rooms_capacity = min($differentRoom);


while($persons>=$min_rooms_capacity)
{
  $tmp = $differentRoom;
  $toSubstract = 0;
  do
  {
    $toSubstract = array_shift($tmp);
  }
  while($toSubstract>$persons);
  echo $toSubstract.',';
  $persons-=$toSubstract;
}

它可以明显改善，但它应该给你如何处理这种情况的建议。我不知道算法的英文名称，但用波兰语直接翻译就是“背包问题”
有关贪婪算法的详细信息：http://en.wikipedia.org/wiki/Greedy_algorithm