3

情况是我必须用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''Room 3''Room 1'

在另一个例子中，我有

$persons = 15;

还有一个数组

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

这次组合不能正好是 15。在这种情况下，结果必须是大于 15 的组合。在这种情况下，它将是 16。16 最接近 10，结果必须是。您需要：“房间 2”“房间 2”“房间 1”

我怎样才能做到这一点？

4

2 回答 2

2

这个问题是 NP 难题，是背包问题的一个变体，重复（http://en.wikipedia.org/wiki/Knapsack_problem了解更多关于该主题的信息）。

值得注意的修改是，您不是试图获得尽可能大的权重，而是试图获得尽可能接近某个值的权重。这可以通过改变权重函数来完成。

最好的解决方案是动态编程，您可能想研究一下。然而，这更像是一个算法/CSci 问题，因此最好将其发布在数学/编程 stackexchange 问题板上。

于 2013-05-16T13:39:40.723 回答
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

于 2013-05-16T13:48:54.690 回答