PHP: задача о ранце 0-1
Это разновидность задачи о рюкзаке (ранце), в которой можно взять не более одного предмета каждого вида. Тестик взял отсюда, вроде бы, совпало.
Скрипт определяет исходные данные в виде массива и выводит результаты в виде разметки HTML, всю работу выполняет единственная рекурсивная функция knapsackSolve.
Ниже прикреплён документ PHP со встроенной разметкой HTML5, предполагается кодировка Юникод (UTF-8).
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Рюкзак 0-1</title>
</head>
<body>
<pre>
#########################################################
# Решение задачи о рюкзаке (ранце) 0-1 (не более 1 предмета каждого вида)
# $w - веса элементов
# $v - стоимость (ценность) элементов
# $i - индекс последнего элемент
# $aW - вместимость (максимальный суммарный вес)
# $m - массив результатов:
# найденная максимальная стоимость; вложенный массив с индексами выбранных элементов
#########################################################
</pre>
<?php
function knapsackSolve($w, $v, $i, $aW, &$m, &$numcalls) {
$numcalls++;
if (isset($m[$i][$aW])) {
return array( $m[$i][$aW], $m['picked'][$i][$aW] );
}
else {
if ($i == 0) {
if ($w[$i] <= $aW) { //Элемент влезет?
$m[$i][$aW] = $v[$i];
$m['picked'][$i][$aW] = array($i);
return array($v[$i],array($i));
}
else {
$m[$i][$aW] = 0; //Не влезает
$m['picked'][$i][$aW] = array();
return array(0,array());
}
}
//Результат не достигнут, смотрим следующую ветвь
list ($without_i, $without_PI) = knapsackSolve($w, $v, $i-1, $aW, $m, $numcalls);
if ($w[$i] > $aW) { //Слишком много?
$m[$i][$aW] = $without_i; //Убрать этот элемент
$m['picked'][$i][$aW] = $without_PI;
return array($without_i, $without_PI);
}
else { //Уменьшить оставшуюся вместимость и смотреть дальше
list ($with_i,$with_PI) = knapsackSolve($w, $v, ($i-1), ($aW - $w[$i]), $m, $numcalls);
$with_i += $v[$i];
//Выбрать большее из WITH и WITHOUT
if ($with_i > $without_i) {
$res = $with_i;
$picked = $with_PI;
array_push($picked,$i);
}
else {
$res = $without_i;
$picked = $without_PI;
}
$m[$i][$aW] = $res; //Запомнить выбранное
$m['picked'][$i][$aW] = $picked;
return array ($res,$picked);
}
}
}
//Данные
$weights = array(23, 31, 29, 44, 53, 38, 63, 85, 89, 82); //Веса элементов
$costs = array(92, 57, 49, 68, 60, 43, 67, 84, 87, 72); //Стоимости элементов
$items4 = array('Yes-1','Yes-2','Yes-3','Yes-4','No-1','Yes-5','No-2','No-3','No-4','No-5'); //Названия элементов
$capacity=165; //ёмкость рюкзака
//Инициализация
$numcalls = 0;
$m = array();
$pickedItems = array();
//Решение
list ($m4,$pickedItems) = knapsackSolve($weights, $costs, sizeof($costs)-1, $capacity, $m, $numcalls);
//Вывод результатов
echo '<p>';
echo '<b>Элементы:</b><br>'.join(', ',$items4).'<br>';
echo "<b>Найденная максимальная стоимость:</b><br>$m4 (количество вызовов функции: $numcalls)<br>";
echo '<b>Индексы элементов:</b><br>'.join(',',$pickedItems).'<br>';
echo '<b>Названия выбранных элементов:</b><br>';
echo '<table border="1" cellspacing="0">';
echo '<tr><td>Элемент</td><td>Стоимость</td><td>Вес</td></tr>';
$totalVal = $totalWt = 0;
foreach($pickedItems as $key) {
$totalVal += $costs[$key];
$totalWt += $weights[$key];
echo '<tr><td>'.$items4[$key].'</td><td>'.$costs[$key].'</td><td>'.$weights[$key].'</td></tr>';
}
echo "<tr><td align=right><b>Итого</b></td><td>$totalVal</td><td>$totalWt</td></tr>";
echo '</table>';
?>
</body></html>
Вот что выводит этот код при тестовых исходных данных:
######################################################### # Решение задачи о рюкзаке (ранце) 0-1 (не более 1 предмета каждого вида) # $w - веса элементов # $v - стоимость (ценность) элементов # $i - индекс последнего элемент # $aW - вместимость (максимальный суммарный вес) # $m - массив результатов: # найденная максимальная стоимость; вложенный массив с индексами выбранных элементов #########################################################Элементы:
Yes-1, Yes-2, Yes-3, Yes-4, No-1, Yes-5, No-2, No-3, No-4, No-5
Найденная максимальная стоимость:
309 (количество вызовов функции: 199)
Индексы элементов:
0,1,2,3,5
Названия выбранных элементов:
Элемент Стоимость Вес Yes-1 92 23 Yes-2 57 31 Yes-3 49 29 Yes-4 68 44 Yes-5 43 38 Итого 309 165
16.09.2018, 11:23 [2442 просмотра]