Рубрики

0-1 Рюкзак Задача | DP-10

Учитывая вес и значения n предметов, поместите эти предметы в рюкзак вместимостью W, чтобы получить максимальную общую стоимость в рюкзаке. Другими словами, даны два целочисленных массива val [0..n-1] и wt [0..n-1], которые представляют значения и веса, связанные с n элементами соответственно. Также, учитывая целое число W, которое представляет вместимость ранца, определите подмножество максимального значения val [], чтобы сумма весов этого подмножества была меньше или равна W. Вы не можете разбить предмет, либо выбрать полный предмет, либо не выбирайте его (0-1 свойство).

Простое решение — рассмотреть все подмножества предметов и рассчитать общий вес и стоимость всех подмножеств. Рассмотрим только те подмножества, общий вес которых меньше W. Из всех таких подмножеств выберите подмножество максимального значения.

1) Оптимальная подструктура:
Чтобы рассмотреть все подмножества элементов, может быть два случая для каждого элемента: (1) элемент включен в оптимальный набор, (2) не включен в оптимальный набор.
Следовательно, максимальное значение, которое можно получить из n элементов, является максимальным из следующих двух значений.
1) Максимальное значение, полученное n-1 предметами и весом W (исключая n-й предмет).
2) Стоимость n-го предмета плюс максимальное значение, полученное из n-1 предметов, и W минус вес n-го предмета (включая n-й предмет).

Если вес n-го предмета больше W, тогда n-й предмет не может быть включен, и случай 1 является единственной возможностью.

2) Перекрывающиеся подзадачи
Ниже приводится рекурсивная реализация, которая просто следует рекурсивной структуре, упомянутой выше.

C ++

/ * Наивная рекурсивная реализация задачи о ранце 0-1 * /
#include <bits/stdc++.h>

using namespace std;

  
// Вспомогательная функция, которая возвращает максимум два целых числа

int max(int a, int b) { return (a > b)? a : b; } 

  
// Возвращает максимальное значение, которое
// можно положить в рюкзак вместимостью W

int knapSack(int W, int wt[], int val[], int n) 

      
// Базовый вариант

if (n == 0 || W == 0) 

    return 0; 

  
// Если вес n-го элемента больше
// чем рюкзак вместимостью Вт, то
// этот элемент не может быть включен
// в оптимальном решении

if (wt[n-1] > W) 

    return knapSack(W, wt, val, n-1); 

  
// Возвращаем максимум двух случаев:
// (1) n-й элемент включен
// (2) не включены

else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1), 

                    knapSack(W, wt, val, n-1) ); 

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

int main() 

    int val[] = {60, 100, 120}; 

    int wt[] = {10, 20, 30}; 

    int W = 50; 

    int n = sizeof(val)/sizeof(val[0]); 

    cout<<knapSack(W, wt, val, n); 

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

/ * Наивная рекурсивная реализация задачи о ранце 0-1 * /
#include<stdio.h>

  
// Вспомогательная функция, которая возвращает максимум два целых числа

int max(int a, int b) { return (a > b)? a : b; }

  
// Возвращает максимальное значение, которое можно положить в рюкзак вместимостью W

int knapSack(int W, int wt[], int val[], int n)

{

   // Базовый вариант

   if (n == 0 || W == 0)

       return 0;

  

   // Если вес n-го предмета больше вместимости рюкзака W, то

   // этот элемент не может быть включен в оптимальное решение

   if (wt[n-1] > W)

       return knapSack(W, wt, val, n-1);

  

   // Возвращаем максимум двух случаев:

   // (1) n-й элемент включен

   // (2) не включены

   else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),

                    knapSack(W, wt, val, n-1)

                  );

}

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

int main()

{

    int val[] = {60, 100, 120};

    int wt[] = {10, 20, 30};

    int  W = 50;

    int n = sizeof(val)/sizeof(val[0]);

    printf("%d", knapSack(W, wt, val, n));

    return 0;

}

Джава

/ * Наивная рекурсивная реализация задачи о ранце 0-1 * /

class Knapsack

{

  

    // Вспомогательная функция, которая возвращает максимум два целых числа

     static int max(int a, int b) { return (a > b)? a : b; }

       

     // Возвращает максимальное значение, которое можно положить в рюкзак вместимостью W

     static int knapSack(int W, int wt[], int val[], int n)

     {

        // Базовый вариант

    if (n == 0 || W == 0)

        return 0;

       

    // Если вес n-го предмета больше вместимости рюкзака W, то

    // этот элемент не может быть включен в оптимальное решение

    if (wt[n-1] > W)

       return knapSack(W, wt, val, n-1);

       

    // Возвращаем максимум двух случаев:

    // (1) n-й элемент включен

    // (2) не включены

    else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),

                     knapSack(W, wt, val, n-1)

                      );

      }

  

    

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

   public static void main(String args[])

   {

        int val[] = new int[]{60, 100, 120};

        int wt[] = new int[]{10, 20, 30};

    int  W = 50;

    int n = val.length;

    System.out.println(knapSack(W, wt, val, n));

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

питон

# Наивная рекурсивная реализация задачи о ранце 0-1

  
# Возвращает максимальное значение, которое можно положить в рюкзак
# мощность Вт

def knapSack(W , wt , val , n):

  

    # Базовый вариант

    if n == 0 or W == 0 :

        return 0

  

    # Если вес n-го предмета больше ранца вместимости

    # W, то этот пункт не может быть включен в оптимальное решение

    if (wt[n-1] > W):

        return knapSack(W , wt , val , n-1)

  

    # вернуть максимум два случая:

    # (1) n-й предмет включен

    # (2) не включены

    else:

        return max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1),

                   knapSack(W , wt , val , n-1))

  
# конец функции knapSack

  
# Для проверки вышеуказанной функции

val = [60, 100, 120]

wt = [10, 20, 30]

W = 50

n = len(val)

print knapSack(W , wt , val , n)

  
# Этот код предоставлен Nikhil Kumar Singh

C #

/ * Наивная рекурсивная реализация
0-1 проблема с рюкзаком * /

using System;

  

class GFG {

      

    // Вспомогательная функция, которая возвращает

    // максимум двух целых

    static int max(int a, int b) 

    {

        return (a > b)? a : b; 

    }

      

    // Возвращает максимальное значение, которое может

    // положить в рюкзак вместимостью W

    static int knapSack(int W, int []wt, 

                        int []val, int n)

    {

          

        // Базовый вариант

        if (n == 0 || W == 0)

            return 0;

      

        // Если вес n-го элемента

        // больше, чем вместимость ранца W,

        // тогда этот элемент не может быть

        // входит в оптимальное решение

        if (wt[n-1] > W)

            return knapSack(W, wt, val, n-1);

          

        // Возвращаем максимум двух случаев:

        // (1) n-й элемент включен

        // (2) не включены

        else return max( val[n-1] +

            knapSack(W-wt[n-1], wt, val, n-1),

                   knapSack(W, wt, val, n-1));

    }

  

    // Функция драйвера

    public static void Main()

    {

        int []val = new int[]{60, 100, 120};

        int []wt = new int[]{10, 20, 30};

        int W = 50;

        int n = val.Length;

          

        Console.WriteLine(knapSack(W, wt, val, n));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// Наивная рекурсивная реализация
// из 0-1 задачи о ранце

  
// Возвращает максимальное значение, которое
// можно положить в рюкзак
// мощность Вт

function knapSack($W, $wt, $val, $n)

{

    // Базовый вариант

    if ($n == 0 || $W == 0)

        return 0;

      

    // Если вес n-го элемента

    // больше, чем вместимость рюкзака

    // W, то этот элемент не может быть

    // входит в оптимальное решение

    if ($wt[$n - 1] > $W)

        return knapSack($W, $wt, $val, $n - 1);

      

    // Возвращаем максимум двух случаев:

    // (1) n-й элемент включен

    // (2) не включены

    else

        return max($val[$n - 1] + 

               knapSack($W - $wt[$n - 1], 

               $wt, $val, $n - 1), 

               knapSack($W, $wt, $val, $n-1));

}

  

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

    $val = array(60, 100, 120);

    $wt = array(10, 20, 30);

    $W = 50;

    $n = count($val);

    echo knapSack($W, $wt, $val, $n);

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


Выход:

220

Следует отметить, что вышеуказанная функция снова и снова вычисляет одни и те же подзадачи. Смотрите следующее дерево рекурсии, K (1, 1) оценивается дважды. Временная сложность этого наивного рекурсивного решения является экспоненциальной (2 ^ n).

In the following recursion tree, K() refers to knapSack().  The two 
parameters indicated in the following recursion tree are n and W.  
The recursion tree is for following sample inputs.
wt[] = {1, 1, 1}, W = 2, val[] = {10, 20, 30}

                       K(3, 2)         ---------> K(n, W)
                   /            \ 
                 /                \               
            K(2,2)                  K(2,1)
          /       \                  /    \ 
        /           \              /        \
       K(1,2)      K(1,1)        K(1,1)     K(1,0)
       /  \         /   \          /   \
     /      \     /       \      /       \
K(0,2)  K(0,1)  K(0,1)  K(0,0)  K(0,1)   K(0,0)
Recursion tree for Knapsack capacity 2 units and 3 items of 1 unit weight.

Поскольку подзадачи оцениваются снова, эта проблема имеет свойство Перекрывающиеся подзадачи. Таким образом, задача 0-1 о ранце имеет оба свойства (см. Это и это ) задачи динамического программирования. Как и в других типичных задачах динамического программирования (DP) , повторных вычислений с одинаковыми подзадачами можно избежать, построив временный массив K [] [] в порядке снизу вверх. Ниже приводится реализация на основе динамического программирования.

C ++

// Решение на основе динамического программирования для задачи о ранце 0-1
#include<stdio.h>

  
// Вспомогательная функция, которая возвращает максимум два целых числа

int max(int a, int b) { return (a > b)? a : b; }

  
// Возвращает максимальное значение, которое можно положить в рюкзак вместимостью W

int knapSack(int W, int wt[], int val[], int n)

{

   int i, w;

   int K[n+1][W+1];

  

   // Построить таблицу K [] [] снизу вверх

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

   {

       for (w = 0; w <= W; w++)

       {

           if (i==0 || w==0)

               K[i][w] = 0;

           else if (wt[i-1] <= w)

                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);

           else

                 K[i][w] = K[i-1][w];

       }

   }

  

   return K[n][W];

}

  

int main()

{

    int val[] = {60, 100, 120};

    int wt[] = {10, 20, 30};

    int  W = 50;

    int n = sizeof(val)/sizeof(val[0]);

    printf("%d", knapSack(W, wt, val, n));

    return 0;

}

Джава

// Решение на основе динамического программирования для задачи о ранце 0-1

class Knapsack

{

  

    // Вспомогательная функция, которая возвращает максимум два целых числа

    static int max(int a, int b) { return (a > b)? a : b; }

       

   // Возвращает максимальное значение, которое можно положить в рюкзак вместимостью W

    static int knapSack(int W, int wt[], int val[], int n)

    {

         int i, w;

     int K[][] = new int[n+1][W+1];

       

     // Построить таблицу K [] [] снизу вверх

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

     {

         for (w = 0; w <= W; w++)

         {

             if (i==0 || w==0)

                  K[i][w] = 0;

             else if (wt[i-1] <= w)

                   K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);

             else

                   K[i][w] = K[i-1][w];

         }

      }

       

      return K[n][W];

    }

  

    

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

    public static void main(String args[])

    {

        int val[] = new int[]{60, 100, 120};

    int wt[] = new int[]{10, 20, 30};

    int  W = 50;

    int n = val.length;

    System.out.println(knapSack(W, wt, val, n));

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

питон

# Программа Python на основе динамического программирования для задачи о ранце 0-1
# Возвращает максимальное значение, которое можно положить в рюкзак вместимостью W

def knapSack(W, wt, val, n):

    K = [[0 for x in range(W+1)] for x in range(n+1)]

  

    # Построить таблицу K [] [] снизу вверх

    for i in range(n+1):

        for w in range(W+1):

            if i==0 or w==0:

                K[i][w] = 0

            elif wt[i-1] <= w:

                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])

            else:

                K[i][w] = K[i-1][w]

  

    return K[n][W]

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

val = [60, 100, 120]

wt = [10, 20, 30]

W = 50

n = len(val)

print(knapSack(W, wt, val, n))

  
# Этот код предоставлен Bhavya Jain

C #

// Решение на основе динамического программирования для
// 0-1 проблема с ранцем

using System;

  

class GFG {

      

    // Вспомогательная функция, которая возвращает

    // максимум двух целых

    static int max(int a, int b)

    {

        return (a > b) ? a : b;

    }

      

    // Возвращает максимальное значение, которое

    // можно положить в рюкзак

    // мощность Вт

    static int knapSack(int W, int []wt, 

                         int []val, int n)

    {

        int i, w;

        int [,]K = new int[n+1,W+1];

          

        // Строим таблицу K [] [] внизу

        // вверх

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

        {

            for (w = 0; w <= W; w++)

            {

                if (i == 0 || w == 0)

                    K[i,w] = 0;

                else if (wt[i-1] <= w)

                    K[i,w] = Math.Max(val[i-1] 

                           + K[i-1,w-wt[i-1]],

                                    K[i-1,w]);

                else

                    K[i,w] = K[i-1,w];

            }

        }

          

        return K[n,W];

    }

      

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

    static void Main()

    {

        int []val = new int[]{60, 100, 120};

        int []wt = new int[]{10, 20, 30};

        int W = 50;

        int n = val.Length;

          

        Console.WriteLine(

                  knapSack(W, wt, val, n));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// Решение на основе динамического программирования
// для задачи о ранце 0-1

  
// Возвращает максимальное значение, которое
// можно положить в рюкзак
// мощность Вт

function knapSack($W, $wt, $val, $n)

{

      

    $K = array(array());

      

    // Строим таблицу K [] [] в

    // снизу вверх

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

    {

        for ($w = 0; $w <= $W; $w++)

        {

            if ($i == 0 || $w == 0)

                $K[$i][$w] = 0;

            else if ($wt[$i - 1] <= $w)

                    $K[$i][$w] = max($val[$i - 1] + 

                                     $K[$i - 1][$w

                                     $wt[$i - 1]], 

                                     $K[$i - 1][$w]);

            else

                    $K[$i][$w] = $K[$i - 1][$w];

        }

    }

      

    return $K[$n][$W];

}

  

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

    $val = array(60, 100, 120);

    $wt = array(10, 20, 30);

    $W = 50;

    $n = count($val);

    echo knapSack($W, $wt, $val, $n);

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


Выход:

220

Сложность времени: O (nW), где n — количество предметов, а W — вместимость ранца.

Ссылки:
http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf
http://www.cse.unl.edu/~goddard/Courses/CSCE310J/Lectures/Lecture8-DynamicProgramming.pdf

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

0-1 Рюкзак Задача | DP-10

0.00 (0%) 0 votes