Русский
Русский
English
Статистика
Реклама

Knapsack problem

Recovery mode Задача о рюкзаке (Knapsack problem) простыми словами

05.06.2021 00:21:43 | Автор: admin

Пару лет назад столкнулся с так называемой задачей о рюкзаке на одном из собеседований, нашел быстренько решение в интернете. Попытался разобрать и.... ничего не понял. Кое как поменял названия переменных, а кто так не делает когда находит готовое решение для home таски? Отправил и забыл как страшный сон. Недавно друг скинул подобную задачу про монеты и в этот раз я уже быстренько разобрался с этой когда то, как казалось мне неподъемной задачкой.

Хотел бы отметить книгу Grokking Algorithms автора Aditya Bhargava. У нее прям максимально простым языком расписаны основы алгоритмов. Так что если, вы как и я в универе думали что алгоритмы вам никогда не пригодятся, потому что FAANG это не для вас. То я вас и разочарую и обрадую, попасть туда может каждый, если конечно приложит достаточно усилий, ну а разочарую тем что вам конечно придется поднапрячься и осилить алгоритмы и чем раньше вы начнете это делать, тем лучше.

На хабре, уже есть одна статья на эту тему: Алгоритм решения задачи о рюкзаке ( версия 2, исправленная) / Хабр (habr.com) . Но, да простит меня автор, на мой взгляд она совершенно непонятная.

И так, перейду к делу. Сначала расскажу обо всем на пальцах, а потом мы рассмотрим решение на нашем любимом C#.

Собственно задача, одна из популярных её вариаций. Вор пробрался в ювелирный магазин, у него есть рюкзак объемом 4 единицы. В магазине, он увидел три вещи:

Вещи которые есть в магазинеВещи которые есть в магазине

Его задача оптимально уместить эти вещи в рюкзаке так что бы он унес драгоценностей на максимальную стоимость.

Есть несколько способов решения. Один из них это перебор всех вариантов.

Для простоты, предмета будет только три, поскольку количество различных комбинаций в которых их можно унести растет очень быстро и даже для 3 предметов уже будет равно 8. Оно вычисляется по формуле 2n где n - количество предметов, то есть если предмета будет 4, то количество возможных комбинаций достигнет уже 16 и так далее. Такой вариант нас не устроит поскольку решая эту задачу онлайн на каком-нибудь Codility ваше решение зарубят с Timeout Exceeded. Нужно что-то получше.

Мы будем решать эту задачу методом динамического программирования

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

Заполним небольшую табличку:

1

2

3

4

Ожерелье / 4000 / 4 ед

Кольцо / 2500 / 1 ед

Подвеска / 2000 / 3 ед

С левой стороны у нас будут все вещи. При этом порядок в котором они расположены, в данной задаче нас не интересует. Количество колонок равно количеству потенциальных рюкзаков размером от 1, минимально возможного целого положительного числа, до размера нашего рюкзака, с шагом 1. Таким образом мы пытаемся решить ряд более мелких задач, для рюкзаков размером 1, 2, 3 и 4. Всегда ведь проще начинать с малого?)

1

2

3

4

Ожерелье / 4000 / 4 ед

0

0

0

4000

Сверху у нас заполненный первый ряд. Мы можем использовать в каждом ряду, только вещь из этого ряда или вещи из верхних рядов.

Рюкзак размером 1: Ожерелье не влезет в рюкзак, значит стоимость того что мы можем унести равна 0.

Рюкзак размером 2: Ожерелье не влезет в рюкзак, значит стоимость того что мы можем унести равна 0.

Рюкзак размером 3: Ожерелье не влезет в рюкзак, значит стоимость того что мы можем унести равна 0.

Рюкзак размером 4: Здесь все становится немного интересней, вес ожерелья 4 и размер рюкзака 4. Ура, наконец то успех, мы не зря ворвались в магазин, кладем ожерелье в большой рюкзак и убегаем.

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

1

2

3

4

Ожерелье / 4000 / 4 ед

0

0

0

4000

Кольцо / 2500 / 1 ед

2500

2500

2500

4000

Добавилось кольцо. Делаем подсчеты для второго ряда:

Рюкзак размером 1: У нас добавилось кольцо и его размер как раз равен размеру даже самого маленького рюкзака. Но у нас ведь еще есть и ожерелье, мы уже проверили, оно не влезет. Кладем только кольцо.

Рюкзак размером 2: То же что и для размера 1. Кладем только кольцо.

Рюкзак размером 3: То же что и для размера 1. Кладем только кольцо.

Рюкзак размером 4: Здесь у нас есть выбор, либо положить только одно маленькое кольцо, либо взять ожерелье, которое тяжелее, но и стоит дороже. Забываем про кольцо, и возвращаемся за ожерельем!

Так, наконец добавим третий ряд

1

2

3

4

Ожерелье / 4000 / 4 ед

0

0

0

4000

Кольцо / 2500 / 1 ед

2500

2500

2500

4000

Подвеска / 2000 / 3 ед

2500

2500

2500

4500

Рюкзак размером 1: Кольцо дороже подвески, да и подвеска не влезет, она по всем параметрам проигрывает вещам выше, берем кольцо размером 1.

Рюкзак размером 2: Тоже самое что и для размера 1.

Рюкзак размером 3: Несмотря на то что мы можем здесь взять подвеску, кольцо выигрывает ее по параметрам, снова кладем ее.

Рюкзак размером 4: А вот тут у нас, весь рюкзак, и все возможные вещи. И мы видим что кольцо и подвеска вместе стоят на 500 долларов дороже ожерелья и при этом все так же влезут в рюкзак. Значит мы возьмем и кольцо и подвеску стоимостью 4500 и весом как раз 4 единицы.

В правом нижнем углу у нас верный результат.

Ну и где же здесь пере использование спросите вы? Да, мы им не пользовались, потому что таблица была сравнительно простая. Но, если присмотреться то можно заметить закономерность!

Представим что для количества вещей у нас счетчик i, а для рюкзаков j.

На примере последней ячейки рассмотрим формулу в действии

Зеленым выделена первая опция, красным вторая. Как видим стоимость в красном круге перевешивает стоимость в зеленомЗеленым выделена первая опция, красным вторая. Как видим стоимость в красном круге перевешивает стоимость в зеленом

Это работает с любой ячейкой, даже в первом ряду. Просто представьте что у нас есть воображаемый нулевой ряд с нулевыми значениями.

И собственно алгоритм задачи на языке C#:

public static int[] weights = { 4, 1, 3 };public static int[] values = { 4000, 2500, 2000 };public static int CountMax(int[] weights, int[] values, int maxCapacity){    //строим массив и закладываем место на ячейки пустышки     //выходящие из левого верхнего угла    int[,] arr = new int[weights.Length + 1, maxCapacity + 1];    //проходим по всем вещам    for (int i = 0; i <= weights.Length; i++)    {        //проходим по всем рюкзакам        for (int j = 0; j <= maxCapacity; j++)        {            //попадаем в ячейку пустышку            if (i == 0 || j == 0)            {                arr[i, j] = 0;            }            else            {                   //если вес текущей вещи больше размера рюкзака                //казалось бы откуда значение возьмется для первой вещи                 //при таком условии. А оно возьмется из ряда пустышки                if (weights[i - 1] > j)                {                    arr[i, j] = arr[i - 1, j];                }                else                {                    //здесь по формуле. Значение над текущей ячейкой                    var prev = arr[i - 1, j];                    //Значение по вертикали: ряд вверх                    //и по горизонтали: вес рюкзака - вес текущей вещи                    var byFormula = values[i - 1] + arr[i - 1, j - weights[i - 1]];                    arr[i, j] = Math.Max(prev, byFormula);                }            }        }    }    // возвращаем правую нижнюю ячейку    return arr[weights.Length, maxCapacity];}

Всем побед и удачных собесов!

Подробнее..
Категории: Алгоритмы , C , Net , Algorithms , Knapsack problem

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru