Я нашел проблему ранца сложной и интересной одновременно. Я уверен, что если вы посещаете эту страницу, вы уже знаете формулировку проблемы, но только для завершения:
Проблема:
Учитывая рюкзак с максимальной вместимостью W и N предметов, каждый со своим собственным значением и весом, добавьте предметы в рюкзак так, чтобы конечное содержимое имело максимальное значение. Yikes !!!
Вот общий способ объяснения проблемы: представьте себе, что вор грабит дом и несет рюкзак. В доме есть фиксированное количество предметов — каждый со своим весом и ценностью — Ювелирные изделия, с меньшим весом и наибольшей ценностью по сравнению с таблицами, с меньшей ценностью, но намного тяжелее. Чтобы подлить масла в огонь, у вора есть старый рюкзак, емкость которого ограничена. Очевидно, он не может разделить стол на половину или украшения на 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 строки. Это просто означает, что в доме нет предметов. Что вы держите в своем рюкзаке, если нет предметов? Больше ничего !!! Все нули.
Решение:
- Теперь давайте начнем заполнять массив по строкам. Что означает строка 1 и столбец 1? Что дано по первому предмету (ряду), можете ли вы поместить его в рюкзак вместимостью 1 (колонка) Нет. Вес первого элемента равен 5. Итак, давайте заполним 0. Фактически, мы не сможем заполнить что-либо, пока не достигнем столбца 5 (вес 5).
- Как только мы достигнем столбца 5 (который представляет вес 5) в первой строке, это означает, что мы могли бы разместить элемент 1. Давайте заполним там 10 (помните, это массив значений):
- Переходя к весу 6 (столбец 6), можем ли мы приспособить что-либо еще с оставшимся весом 1 (вес — вес этого предмета => 6 — 5). Эй, помни, мы на первом месте. Таким образом, довольно интуитивно понятно, что остальная часть строки будет иметь одинаковое значение, поскольку мы не можем добавить какой-либо другой элемент для того дополнительного веса, который у нас есть.
- Итак, следующая интересная вещь происходит, когда мы достигаем столбца 4 в третьем ряду. Текущий рабочий вес 4.
Мы должны проверить следующие случаи.
- Можем ли мы разместить пункт 2 — Да, мы можем. Вес предмета 2 — 4.
- Значение текущего веса выше без пункта 2? — Проверьте предыдущий ряд на тот же вес. Нет. предыдущая строка * содержит 0, так как мы не смогли разместить элемент 1 весом 4.
- Можем ли мы разместить два предмета одинакового веса, чтобы максимально увеличить стоимость? — Нет. Оставшийся вес после вычета веса Item2 равен 0.
Почему предыдущий ряд?
Просто потому, что предыдущий ряд с весом 4 сам по себе является меньшим решением для ранца, который дает максимальное значение, которое может быть накоплено для этого веса до этой точки (прохождение через элементы).
Иллюстрация,
- Стоимость текущего предмета = 40
- Вес текущего элемента = 4
- Вес, который остался больше = 4 — 4 = 0
- Проверьте строку выше (Элемент выше в случае Элемента 1 или совокупное значение Макс в случае остальных строк). Для оставшегося веса 0, мы можем разместить пункт 1? Проще говоря, есть ли какое-либо значение в приведенном выше ряду для данного веса?
Расчет идет так:
- Возьмите максимальное значение для того же веса без этого элемента:
123
previous row, same weight =
0
=> V[item-
1
][weight]
- Возьмем значение текущего элемента + значение, которое мы могли бы согласовать с оставшимся весом:
1234
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).
- Следующее и наиболее важное событие происходит в столбце 9 и строке 2. Это означает, что у нас есть вес 9, и у нас есть два элемента. Глядя на данные примера, мы могли бы разместить первые два пункта. Здесь мы рассмотрим несколько вещей:
1234
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
.
Итак, расчет таков:
- Возьмите максимальное значение для того же веса без этого элемента:
1
previous row, same weight =
10
- Возьмем значение текущего элемента + значение, которое мы могли бы накопить с оставшимся весом:
1234
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:
сложность
Анализировать сложность решения довольно просто. У нас просто есть цикл для 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]; } } |