Knapsack problem или задача о ранце

backpackstrends.com

Думаю, стоит сначала представиться. Я Даниял Загидуллин, по роду деятельности — дизайнер. Но последнее время все чаще я занимаюсь вёрсткой и кодингом.

Для одного из своих проектов мне нужно было изящное решение “Задачи о ранце” (knapsack problem). Её суть, на первый взгляд, довольно проста: у нас есть N-ое количество предметов, каждый из которых весит X килограмм, которые нужно уложить в рюкзак вместимости Y килограмм.

Если представить на примере, то мы легко поймём, что задача довольно проста.

Macbook 1кг, коробка яблок 2кг, книга 0.5кг.
Вместимость рюкзака 1.5кг.

Очевидно, что оптимальным вариантом будет взять Macbook и книгу. Но что если предметов будет больше? Тогда нам нужно писать скрипт.

Русскоязычный интернет молчал по поводу решению данной проблемы на PHP, посему пришлось сходить в англоязычный.
Решение было найдено, хоть и длинное, поэтому я немного его укоротил под свои нужды и выкладываю здесь.

<?php
class Balancer {
public static function balance($items, $key, $maxWeight) {
$result = array();
$numItems = count($items);
$sack = self::buildSack($numItems, $maxWeight);
for ($n = 1; $n <= $numItems; $n++) {
for ($weight = 1; $weight <= $maxWeight; $weight++) {
$a = $sack[$n — 1][$weight][‘value’];
$b = null;
$value = $items[$n — 1][$key];
if ($value <= $weight) {
$b = $value + $sack[$n — 1][$weight — $value][‘value’];
}
$sack[$n][$weight][‘value’] = ($b === null ? $a : max($a, $b));
$sack[$n][$weight][‘take’] = ($b === null ? false : $b > $a);
}
}
$setA = array();
for ($n = $numItems, $weight = $maxWeight; $n > 0; $n — ) {
$item = $items[$n — 1];
$value = $item[$key];
if ($sack[$n][$weight][‘take’]) {
$setA[] = $item;
$weight = $weight — $value;
}
}
return array($setA);
}
protected static function buildSack($width, $height) {
$sack = array();
for ($x = 0; $x <= $width; $x++) {
$sack[$x] = array();
for ($y = 0; $y <= $height; $y++) {
$sack[$x][$y] = array(
‘value’ => 0,
‘take’ => false
);
}
}
return $sack;
}
}
$players = array(
array(‘time’ => 3),
array(‘time’ => 2),
array(‘time’ => 8),
array(‘time’ => 5)
);
$maxWeight = 12;
$sets = Balancer::balance($players, ‘time’, $maxWeight);
$setA = $sets[0];
$sum = 0;
foreach ($setA as $player) {
$sum = $player[‘time’];
echo $sum;
}
?>

Спасибо, что дочитали до этого места :)
На Medium я новичок, но искренне хочу, чтобы это был не последний текст здесь.

Всегда ваш, Даня.

dnzg.ru