代码之家 › 专栏 › 技术社区 › Rupert Madden-Abbott

我怎样才能在y人中间分发x个蛋糕?

php

0

Rupert Madden-Abbott · 技术社区 · 16 年前

我有一个ID为x蛋糕的数组和另一个ID为y人的关联数组。我想确保每个蛋糕正好有两个人享用,每个人都能得到公平的蛋糕份额。然而,蛋糕必须保持完整(即,如果每个人的平均蛋糕是一个分数,那么这个分数对于一些人来说是四舍五入的,而对于其他人来说是四舍五入的)。同一块蛋糕不能分配给任何人两次。例如:

$cake = array(''1','2')
$people = array('1','2','3')

为了做到这一点,我希望创建一个新的数组,其中每一行代表一个蛋糕人分配。由于每个蛋糕被分配给两个人,所以这个表中的行数应该正好是蛋糕数的两倍。这个问题没有一个解决方案,但上面例子的解决方案是:

$cake_person = array(
    '1'=>array('1', '1'),
    '2'=>array('1', '2'),
    '3'=>array('2', '2'),
    '4'=>array('2', '3'),
    )

如何为更多的人和蛋糕可靠地生成这样的解决方案?

数据

//Create people array with 25 people
$people = range(1,25);

//Create cake array with 77 cakes
$cake = range(1,77);

代码

$people_cakes = array();
$totalPeople = count($people);
$idp = 0;

foreach($cakes as $cake) {
    $id1 = $idp % $totalPeople;
    $id2 = ($idp + 1) % $totalPeople;
    $people_cakes[] = array($people[$id + 1], $cake);
    $people_cakes[] = array($people[$id + 2], $cake);

    $idp = $idp + 2;
    }

2 回复 | 直到 16 年前

1

2

Artefacto 16 年前

实现一个算法,迭代蛋糕并按顺序分配零件:

从idp=0开始
反复浏览蛋糕
- 将后半部分交给存储在人员数组位置((idp+1)mod total persons)的人员。
- 总计2至idp

$cakes = range(1, 77);
$people = range(1,25);

$result = array();
$idp = 0;
foreach ($cakes as $cid) {
    $result[] = array(
        'cake_id' => $cid,
        'person_id' => $people[$idp % count($people)],
    );
    $result[] = array(
        'cake_id' => $cid,
        'person_id' => $people[($idp+1) % count($people)]
    );
    $idp += 2;
}


$total = array();
foreach ($result as $a) {
    if (!array_key_exists($a['person_id'], $total)) {
        $total[$a['person_id']] = 0;
    }
    $total[$a['person_id']]++;
}

var_dump($total); //gives the number of halves per person

2

0

nico 16 年前

让我们以77个蛋糕和25个人为例。

如果每个蛋糕有两个人吃,要养活25个人你需要12.5个蛋糕。我们会很慷慨,让它成为13(即使用 ceiling

77 / 13 = 5.92 给每个人送蛋糕。 minCakes

所以现在你知道每个人都应该 小蛋糕

现在你一次迭代2个人

给1人和2人1到2块蛋糕 小蛋糕

给人3块和4块蛋糕 minCakes + 1 到 minCakes * 2 + 1

....

在我们的例子中,25个人是孤独的:(,所以他会得到他的把蛋糕和一半给1号的人 小蛋糕

基本上,n和n+1会有蛋糕 minCakes * floor(n/2) + 1 到 minCakes * floor(n/2) + minCakes

小蛋糕 人。

现在是时候分配剩下的了。在我们的情况下 5 * 24/2 = 60 加上25个人的5个蛋糕,我们总共用了65个蛋糕,所以 77 - 65 = 12

你可以从数字1(如果人数是偶数)或者,像我们的例子一样,从数字1开始分发 minCakes+1