dynamic-programming
배낭 문제

algorithm C Language C# Language C++ Haskell Language Java Language JavaScript PHP Python Language Scala Language
수색…


비고

배낭 문제 또는 배낭 문제는 조합 최적화 에서 문제입니다. 각각 가중치 W 값이있는 항목 세트가 주어진 경우,] 렉션에 포함 할 각 항목의 수를 판별하여 Q 가중치가 주어진 한계보다 작거나 같고 Q 값이 가능한 큰 값이되도록하십시오. 고정 크기 배낭으로 제한되는 사람이 직면 한 문제에서 이름을 파생시키고 가장 가치있는 항목으로 채워야합니다.

이 문제는 재정적 인 제약이 있고 조합론 , 컴퓨터 과학 , 복잡성 이론 , 암호학 , 응용 수학 및 일일 판타지 스포츠 와 같은 분야에서 연구되는 자원 배분에서 종종 발생합니다.

배낭 문제는 1897 년까지 거슬러 올라가는 초기 작품으로 1 세기 이상 연구되었습니다. "배낭 문제"라는 이름은 수학자 Tobias Dantzig (1884-1956)의 초기 작품으로 거슬러 올라갑니다. 짐을 과부하하지 않고 가장 중요하거나 유용한 물건을 포장하십시오.

0-1 배낭 문제

배낭을 휴대 할 수있는 총 무게와 체중과 가치가있는 아이템을 고려해 볼 때, 어떻게하면 값 합계가 최대가되지만 무게가 합계가되지 않는 방식으로 아이템을 가져갈 수 있습니까? 당신이 나를 수있는 총 무게를 초과하지 않습니까? 0-1 은 항목을 선택했거나 선택하지 않았 음을 나타냅니다. 또한 우리는 각 항목마다 하나의 수량을 가지고 있습니다. 즉, 항목을 분리 할 수 ​​없다는 의미입니다. 0-1 배낭 문제 가 아니라면 아이템을 분리 할 수 ​​있었다는 것을 의미합니다. 즉, 부분 배낭 문제 라고하는 탐욕스러운 해결책이 있습니다 .

이제는 당면한 문제에 집중하겠습니다. 예를 들어 배낭의 용량이 7 이라고 가정 해 봅시다. 우리는 4 항목 있습니다. 그들의 가중치와 가치는 : 

+----------+---+---+---+---+
|   Item   | 1 | 2 | 3 | 4 |
+----------+---+---+---+---+
|  Weight  | 1 | 3 | 4 | 5 |
+----------+---+---+---+---+
|   Value  | 1 | 4 | 5 | 7 |
+----------+---+---+---+---+

한 가지 무차별 대항법은 가능한 모든 항목 조합을 취하는 것입니다. 그런 다음 우리는 총 무게를 계산할 수 있으며 배낭의 용량을 초과하여 배제하고 최대 가치를 제공하는 배합을 찾을 수 있습니다. 4 개 항목에 대해 ( 4! - 1 ) = 23 개의 가능한 조합 (항목이없는 조합 제외)을 확인해야합니다. 아이템 수가 증가 할 때 이것은 상당히 성가시다. 여기, 우리가 알아 차릴 수있는 몇 가지 측면, 즉 :

  • 우리는보다 적은 항목을 가져 와서 해당 항목을 사용하여 얻을 수있는 최대 값을 계산하고 결합 할 수 있습니다. 그래서 우리의 문제는 하위 문제로 나눌 수 있습니다.
  • 항목 {1,2}에 대한 조합을 계산하면 {1, 2, 3}을 계산할 때 사용할 수 있습니다.
  • 무게를 최소화하고 가치를 극대화하면 최적의 솔루션을 찾을 수 있습니다.

이러한 이유로 동적 프로그래밍을 사용하여 문제를 해결합니다. 우리의 전략은 다음과 같습니다 : 새로운 아이템이 올 때마다 우리는 아이템을 선택할 수 있는지 확인한 다음 다시 최대 값을주는 아이템을 선택합니다. 이제 항목을 선택하면 값은 항목의 값과 용량에서 값을 뺀 값과 나머지 무게로 얻을 수있는 값의 최대 값이됩니다. 항목을 선택하지 않으면 항목을 포함하지 않고 최대 가치를 제공하는 항목을 선택합니다. 우리의 예를 들어 이해하자.

우리는 2D 배열 테이블을 취할 것입니다. 여기서 열의 수는 항목 +1을 취함으로써 얻을 수있는 최대 값이 될 것입니다. 그리고 행의 수는 항목의 수와 같을 것입니다. 우리 배열은 다음과 같습니다. 

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

편의를 위해 각 항목의 무게와 가치를 배열에 통합했습니다. 이들은 배열의 일부가 아니라는 것을 기억하십시오. 이것들은 계산 목적으로 만 사용됩니다.이 값을 테이블 배열에 저장할 필요는 없습니다.

첫 번째 열은 0 으로 채워집니다. 우리가 가지고있는 아이템이 무엇이든 관계없이 최대 용량이 0 이라면 아이템을 선택할 수 없으므로 최대 값은 0이 됩니다. Table [0] [1] 부터 살펴 보겠습니다. 표 [1] [1]을 채울 때, 최대 용량이 1 이고 첫 번째 항목 만 가지고 있다면 최대 값은 무엇입니까? 우리가 할 수있는 최선의 방법은 항목을 선택하여 1 입니다. Table [0] [2]의 경우 최대 용량이 2 이고 첫 번째 항목 만있는 경우 최대 값은 1 입니다. 이는 Table [0] [3] , Table [0] [4] , Table [0] [5] , Table [0] [6] 및 Table [0] [7]에 대해서도 동일합니다. 이것은 우리에게 가치 1 을주는 항목이 하나뿐이기 때문입니다. 우리가 각 항목의 수량을 1 개만 가지고 있기 때문에, 배낭의 용량을 어떻게 증가시킬지라도, 항목 하나에서 1 은 우리가 할 수있는 최상의 가치입니다. 따라서 배열은 다음과 같습니다. 

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

[1] [1] 에 대해 항목 1 과 2가 있고 배낭의 최대 용량이 1 인 경우 우리가 얻을 수있는 최대 값은 무엇인가? 항목 1 과 2를 모두 쓰면 총 무게가 4 가되어 현재 배낭 용량을 초과합니다. 따라서 항목 2 는 선택할 수 없습니다. 이제 2 번 항목을 쓰지 않고 할 수있는 최선의 방법은 무엇입니까? 맨 위의 값, 즉 최대 용량이 1 이고 두 번째 항목을 선택하지 않은 경우 얻을 수있는 최대 값을 포함하는 Table [0] [1] 입니다. Table [1] [2]의 경우 , 2 가 weight [2] 보다 작으므로 두 번째 항목의 가중치이므로 항목을 가져올 수 없습니다. 따라서 현재 항목의 가중치가 최대 용량보다 큰 경우 해당 항목을 가져올 수 없습니다. 이 경우 상단에서 값을 가져 오며 항목을 제외 할 수있는 최대 값을 나타냅니다. 

if weight[i] > j
    Table[i][j] := Table[i-1][j]
end if

이제 Table [1] [3]에 대한 우리의 최대 용량은 현재의 무게와 같기 때문에 두 가지 선택이 있습니다.

  • 우리는 항목을 선택하고이 항목을 취한 후 다른 나머지 항목에서 얻을 수있는 최대 값으로 값을 추가합니다.
  • 이 항목은 제외 할 수 있습니다.

두 가지 선택 중에서 우리는 최대 가치를 얻을 수있는 것을 선택합니다. 항목을 선택하면이 항목의 값 +이 항목을 취한 후 나머지 항목의 최대 값 = 4 + 0 = 4가 됩니다. 우리는 체중 배열에서 4 (항목의 가치)를 얻고 0 (이 항목을 취한 후 나머지 항목에서 얻을 수있는 최대 값)은 위의 1 단계와 3 단계 뒤로 돌아서옵니다. 그것은 Table [0] [0] 입니다. 왜? 항목을 가져 가면 나머지 용량은 3 - 3 = 0이 되고 남은 항목은 첫 번째 항목이됩니다. 글쎄, Table [0] [0] 이 우리의 용량이 0 이고 우리가 첫 번째 아이템 만 가지고 있다면 얻을 수있는 최대 값을 저장한다는 것을 기억하십시오. 이제 항목을 선택하지 않으면 얻을 수있는 최대 값은 위의 1 단계에서 나온 값인 1 입니다. 이제 우리는이 두 값 ( 4 , 1 )의 최대 값을 취하여 Table [1] [2] = 4로 설정 합니다. 표 [1] [4]의 경우 4 , 최대 배낭 용량이 3 보다 커야합니다. 현재 항목의 무게입니다. 다시 두 가지 옵션이 있습니다. 우리가 취할 맥스 (중량 [2] + [표 0] [4 중량 [2], [표 0] [4]) = 최대 (중량 [2] + [표 0] [1], [표 0] [4] ) = max ( 4 + 1 , 1 ) = 5 이다. 

if weight[i] <= j
    w := weight[i]
    Table[i][j] := max(w + Table[i][j-w], Table[i-1][j])
end if

이 두 수식을 사용하여 전체 테이블 배열을 채울 수 있습니다. 우리 배열은 다음과 같습니다. 

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 | 1 | 1 | 4 | 5 | 5 | 5 | 5 |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 | 1 | 1 | 4 | 5 | 6 | 6 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 | 1 | 1 | 4 | 5 | 7 | 8 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+

여기서 우리가 배열에 삽입 한 마지막 값인 Table [3] [7] 에는 필요한 최대 값이 들어 있습니다. 이것은 우리가 4 개의 품목이 있고 배낭의 우리의 최대 수용량이 7 인 경우에 우리가 얻을 수있는 최대 가치이다.

여기에 우리가 기억해야 할 것은 한 열의 경우에도 체중이 배낭의 용량보다 클 수 있다는 것입니다. 첫 번째 행을 채우는 동안 값을 확인하기위한 또 다른 제약 조건을 유지해야합니다. 또는 다른 행을 가져 와서 첫 번째 행의 모든 ​​값을 0으로 설정할 수 있습니다. 의사 코드는 다음과 같습니다. 

Procedure Knapsack(Weight, Value, maxCapacity):
n := Item.size - 1
Table[n+1][maxCapacity+1]
for i from 0 to n
    Table[i][0] := 0
end for
for j from 1 to maxCapacity
    if j >= Weight[0]
        Table[0][j] := Weight[0]
    else
        Table[0][j] := 0
    end if
end for
for i from 1 to n
    for j from 1 to maxCapacity
        if Weight[i] >= j                                            //can't pick the item
            Table[i][j] := Table[i-1][j]        
        else                                                        //can pick the item
            w := Weight[i]
            Table[i][j] := max(w + Table[i-1][j-w], Table[i-1][j])
        end if
    end for
end for
Return Table[n][maxCapacity]

이 알고리즘의 시간 복잡도는 O(n*maxCapacity) . 여기서 n 은 아이템의 수이고 maxCapacity 는 우리의 배낭의 최대 용량입니다.

지금까지 우리의 예에서 얻을 수있는 최대의 가치를 발견했습니다. 하나의 질문이 아직 남아 있습니다. 실제 상품이란 무엇입니까? 우리는 테이블 배열의 값을 추적하여 우리가 취한 항목을 찾아 낼 것입니다. 우리는 두 가지 전략을 따를 것입니다.

  • 모든 항목에 대해 값이 위의 위치에서 오는 경우 현재 항목을 가져 오지 않았습니다. 위의 1 단계로 이동합니다.
  • 값이 위의 위치에서 나오지 않으면 항목을 가져 왔습니다. 그래서 우리는 위의 1 단계와 x 단계 뒤로 가게됩니다. 여기서 x는 현재 항목의 가중치입니다.

의사 코드는 다음과 같습니다. 

Procedure printItems(Table, maxCapacity, Value):
i := Item.size - 1
j := maxCapacity
while j is not equal to 0
    if Table[i][j] is equal to Table[i-1][j]
        i := i - 1
    else
        Print: i
        j := j - weight[i]
        i := i - 1
    end if
end while

우리가 예제를 되짚어 보면 다음과 같은 결과를 얻게됩니다.

후퇴 어레이

이것으로부터 우리는 아이템 2 와 3 을 최대 값으로 가져갈 수 있다고 말할 수 있습니다.



Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow