Рубрики

Программа PHP для решения проблемы подмножества сумм | DP-25

Учитывая набор неотрицательных целых чисел и сумму значений, определите, существует ли подмножество данного набора с суммой, равной данной сумме .
Пример:

Input:  set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output:  True  //There is a subset (4, 5) with sum 9.

<?php
// Рекурсивное решение задачи о подмножестве сумм

  
// Возвращает true, если есть подмножество набора
// с солнцем равным заданной сумме

function isSubsetSum($set, $n, $sum)

{

    // Базовые случаи

    if ($sum == 0)

        return true;

    if ($n == 0 && $sum != 0)

        return false;

      

    // Если последний элемент больше

    // чем сумма, то игнорируем

    if ($set[$n - 1] > $sum)

        return isSubsetSum($set, $n - 1, $sum);

      

    / * иначе, проверьте, может ли сумма быть

       получен любым из следующих

        (а) включая последний элемент

        (б) исключая последний элемент * /

    return isSubsetSum($set, $n - 1, $sum) || 

        isSubsetSum($set, $n - 1, 

                    $sum - $set[$n - 1]);

}

  
// Код драйвера

$set = array(3, 34, 4, 12, 5, 2);

$sum = 9;

$n = 6;

  

if (isSubsetSum($set, $n, $sum) == true)

    echo"Found a subset with given sum";

else

    echo "No subset with given sum";

      
// Этот код предоставлен Anuj_67
?>

Выход:

Found a subset with given sum

Мы можем решить эту проблему в псевдополиномиальное время с помощью динамического программирования.

PHP

<?php
// Решение для динамического программирования
// проблема суммы подмножеств

  
// Возвращает true, если есть подмножество
// set [] с солнцем, равным данной сумме

function isSubsetSum( $set, $n, $sum)

{

    // Значение подмножества [i] [j] будет

    // быть правдой, если есть подмножество

    // устанавливаем [0..j-1] с суммой, равной i

    $subset = array(array());

  

    // Если сумма равна 0, то ответ верен

    for ( $i = 0; $i <= $n; $i++)

        $subset[$i][0] = true;

  

    // Если сумма не равна 0 и набор пуст,

    // тогда ответ ложный

    for ( $i = 1; $i <= $sum; $i++)

        $subset[0][$i] = false;

  

    // Заполняем таблицу подмножеств в нижней части

    // вверх

    for ($i = 1; $i <= $n; $i++)

    {

        for ($j = 1; $j <= $sum; $j++)

        {

            if($j < $set[$i-1])

                $subset[$i][$j] = 

                      $subset[$i-1][$j];

            if ($j >= $set[$i-1])

                $subset[$i][$j] = 

                       $subset[$i-1][$j] || 

                       $subset[$i - 1][$j

                               $set[$i-1]];

        }

    }

  

    / * // раскомментируем этот код для печати таблицы

    для (int i = 0; i <= n; i ++)

    {

    для (int j = 0; j <= sum; j ++)

        printf ("% 4d", подмножество [i] [j]);

    Е ( "п");

    } * /

  

    return $subset[$n][$sum];

}

  
// Программа драйвера для проверки вышеуказанной функции

$set = array(3, 34, 4, 12, 5, 2);

$sum = 9;

$n = count($set);

  

if (isSubsetSum($set, $n, $sum) == true)

    echo "Found a subset with given sum";

else

    echo "No subset with given sum";

  
// Этот код предоставлен anuj_67.
?>

Выход:

Found a subset with given sum

Пожалуйста, ознакомьтесь с полной статьей о проблеме подмножества сумм | DP-25 для более подробной информации!

Рекомендуемые посты:

Программа PHP для решения проблемы подмножества сумм | DP-25

0.00 (0%) 0 votes