Статьи

Проблема с рюкзаком

Ноябрь 19, 2018

Я нашел проблему ранца сложной и интересной одновременно. Я уверен, что если вы посещаете эту страницу, вы уже знаете формулировку проблемы, но только для завершения:

Проблема:

Учитывая рюкзак с максимальной вместимостью W и N предметов, каждый со своим собственным значением и весом, добавьте предметы в рюкзак так, чтобы конечное содержимое имело максимальное значение. Yikes !!!

Knapsack.svg

Вот общий способ объяснения проблемы: представьте себе, что вор грабит дом и несет рюкзак. В доме есть фиксированное количество предметов — каждый со своим весом и ценностью — Ювелирные изделия, с меньшим весом и наибольшей ценностью по сравнению с таблицами, с меньшей ценностью, но намного тяжелее. Чтобы подлить масла в огонь, у вора есть старый рюкзак, емкость которого ограничена. Очевидно, он не может разделить стол на половину или украшения на 3/4. Он либо принимает это, либо оставляет это.

Пример :

1
2
3
4
5
6
7
Knapsack Max weight     :       W = 10 (units)
 
    Total items             :       N = 4
 
    Values of items         :       v[] = {10, 40, 30, 50}
 
    Weight of items         :       w[] = {5, 4, 6, 3}

Беглый взгляд на данные примера показывает нам, что максимальное значение, которое мы могли бы принять с пределом максимального веса 10, составляет 50 + 40 = 90 с весом 7.

Подход:

Способ, которым это оптимально решено, использует динамическое программирование — решение для меньших наборов проблем рюкзака и затем расширение их для большей проблемы

Давайте создадим массив Item x Weight с именем V (массив значений):

1
V[N][W] = 4 rows * 10 columns

Каждое из значений в этой матрице представляет меньшую проблему ранца.

Базовый случай 1 : Давайте возьмем случай 0-го столбца. Это просто означает, что у рюкзака емкость 0. Что вы можете держать в них? Ничего такого. Итак, давайте заполним их все нулями.

Базовый случай 2 : Давайте возьмем случай 0 строки. Это просто означает, что в доме нет предметов. Что вы держите в своем рюкзаке, если нет предметов? Больше ничего !!! Все нули.

Varray0

Решение:

  1. Теперь давайте начнем заполнять массив по строкам. Что означает строка 1 и столбец 1? Что дано по первому предмету (ряду), можете ли вы поместить его в рюкзак вместимостью 1 (колонка) Нет. Вес первого элемента равен 5. Итак, давайте заполним 0. Фактически, мы не сможем заполнить что-либо, пока не достигнем столбца 5 (вес 5).
  2. Как только мы достигнем столбца 5 (который представляет вес 5) в первой строке, это означает, что мы могли бы разместить элемент 1. Давайте заполним там 10 (помните, это массив значений):

    Varray1

  3. Переходя к весу 6 (столбец 6), можем ли мы приспособить что-либо еще с оставшимся весом 1 (вес — вес этого предмета => 6 — 5). Эй, помни, мы на первом месте. Таким образом, довольно интуитивно понятно, что остальная часть строки будет иметь одинаковое значение, поскольку мы не можем добавить какой-либо другой элемент для того дополнительного веса, который у нас есть.

    Varray2

  4. Итак, следующая интересная вещь происходит, когда мы достигаем столбца 4 в третьем ряду. Текущий рабочий вес 4.

Мы должны проверить следующие случаи.

  1. Можем ли мы разместить пункт 2 — Да, мы можем. Вес предмета 2 — 4.
  2. Значение текущего веса выше без пункта 2? — Проверьте предыдущий ряд на тот же вес. Нет. предыдущая строка * содержит 0, так как мы не смогли разместить элемент 1 весом 4.
  3. Можем ли мы разместить два предмета одинакового веса, чтобы максимально увеличить стоимость? — Нет. Оставшийся вес после вычета веса Item2 равен 0.

Varray3

Почему предыдущий ряд?

Просто потому, что предыдущий ряд с весом 4 сам по себе является меньшим решением для ранца, который дает максимальное значение, которое может быть накоплено для этого веса до этой точки (прохождение через элементы).

Иллюстрация,

  1. Стоимость текущего предмета = 40
  2. Вес текущего элемента = 4
  3. Вес, который остался больше = 4 — 4 = 0
  4. Проверьте строку выше (Элемент выше в случае Элемента 1 или совокупное значение Макс в случае остальных строк). Для оставшегося веса 0, мы можем разместить пункт 1? Проще говоря, есть ли какое-либо значение в приведенном выше ряду для данного веса?

Расчет идет так:

  1. Возьмите максимальное значение для того же веса без этого элемента:
    1
    2
    3
    previous row, same weight = 0
     
    => V[item-1][weight]
  2. Возьмем значение текущего элемента + значение, которое мы могли бы согласовать с оставшимся весом:
    1
    2
    3
    4
    Value of current item
    + value in previous row with weight 4 (total weight until now (4) - weight of the current item (4))
     
    => val[item-1] + V[item-1][weight-wt[item-1]]

    Макс среди двух — 40 (0 и 40).

  3. Следующее и наиболее важное событие происходит в столбце 9 и строке 2. Это означает, что у нас есть вес 9, и у нас есть два элемента. Глядя на данные примера, мы могли бы разместить первые два пункта. Здесь мы рассмотрим несколько вещей:
    1
    2
    3
    4
    1. The value of the current item = 40
    2. The weight of the current item = 4
    3. The weight that is left over = 9 - 4 = 5
    4. Check the row above.  At the remaining weight 5, are we able to accommodate Item 1.

    Varray4

Итак, расчет таков:

  1. Возьмите максимальное значение для того же веса без этого элемента:
    1
    previous row, same weight = 10
  2. Возьмем значение текущего элемента + значение, которое мы могли бы накопить с оставшимся весом:
    1
    2
    3
    4
    Value of current item (40)
    + value in previous row with weight 5 (total weight until now (9) - weight of the current item (4))
     
    = 10

    10 против 50 = 50.

В конце решения всех этих небольших проблем нам просто нужно вернуть значение в V [N] [W] — пункт 4 в весе 10:

Varray5

сложность

Анализировать сложность решения довольно просто. У нас просто есть цикл для W внутри цикла N => O (NW)

Реализация:

Вот обязательный код реализации на Java:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Knapsack {
 
    public static void main(String[] args) throws Exception {
        int val[] = {10, 40, 30, 50};
        int wt[] = {5, 4, 6, 3};
        int W = 10;
 
        System.out.println(knapsack(val, wt, W));
    }
 
    public static int knapsack(int val[], int wt[], int W) {
 
        //Get the total number of items.
        //Could be wt.length or val.length. Doesn't matter
        int N = wt.length;
 
        //Create a matrix.
        //Items are in rows and weight at in columns +1 on each side
        int[][] V = new int[N + 1][W + 1];
 
 
        //What if the knapsack's capacity is 0 - Set
        //all columns at row 0 to be 0
        for (int col = 0; col <= W; col++) {
            V[0][col] = 0;
        }
 
        //What if there are no items at home. 
        //Fill the first row with 0
        for (int row = 0; row <= N; row++) {
            V[row][0] = 0;
        }
 
        for (int item=1;item<=N;item++){
 
            //Let's fill the values row by row
            for (int weight=1;weight<=W;weight++){
 
                //Is the current items weight less
                //than or equal to running weight
                if (wt[item-1]<=weight){
 
//Given a weight, check if the value of the current
//item + value of the item that we could afford
//with the remaining weight is greater than the value
//without the current item itself
                    V[item][weight]=Math.max (val[item-1]+V[item-1][weight-wt[item-1]], V[item-1][weight]);
                }
                else {
//If the current item's weight is more than the
//running weight, just carry forward the value
//without the current item
                    V[item][weight]=V[item-1][weight];
                }
            }
 
        }
 
        //Printing the matrix
        for (int[] rows : V) {
            for (int col : rows) {
 
                System.out.format("%5d", col);
            }
            System.out.println();
        }
 
        return V[N][W];
 
    }
 
}
Ссылка: Проблема с рюкзаком от нашего партнера JCG Аруна Маниваннана в блоге Rerun.me .
45
Share: