БлогNot. PHP: задача о ранце 0-1

Помощь дата->рейтинг Поиск Почта RSS канал Статистика nickolay.info Домой

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-19223
Yes-25731
Yes-34929
Yes-46844
Yes-54338
Итого309165


теги: программирование числа php

16.09.2018, 11:23; рейтинг: 101

  свежие записипоиск по блогукомментариистатистикао "вирусах" в архивах .zip

Наверх Яндекс.Метрика
© PerS
вход