[백준/파이썬] 12865 : 평범한 배낭

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

문제 요약 : N개의 물건은 무게와 가치를 가진다. 최대 K만큼의 무게만을 넣을 수 있는 배낭이 있다. 배낭에 넣을 수있는 물건들의 가치의 최대값을 구하라.

 

 

---

Knapsack Problem

배낭문제는 DP에서 굉장히 유명한 알고리즘이다.

처음 이 문제 풀이를 볼 때 이해하는데 굉장히 애를 먹었다.

한번 알고나면 간단한 문제이다.

 

어떤 배낭이 있다. 이 배낭에 넣을 수 있는 최대 무게는 K이다.

배낭에 넣을 수 있는 물건들은 N개가 있다. 이 물건들은 각각 W무게와 V가치를 가지고 있다.

배낭에 넣을 수 있는 물건이 가지는 최대가치를 구하는 문제이다.

 

배낭 문제는 크게 두가지로 나눌 수 있는데,

첫번째는 물건을 쪼갤 수 있는 배낭문제(Fraction Knapsack Problem)이고

두번째는 물건을 쪼갤 수 없는 배낭문제(0/1 Knapsack Problem)이다.

 

첫번째의 경우는 그리디 알고리즘으로 해결할 수 있다.

이번에 초점을 맞출 내용은 두번째 내용이다. 

 

접근법 1) Brute Force -  브루트 포스, 전체 탐색

• 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만을 가져온다.
• 모든 영역을 전체 탐색
• 선형 구조를 전체적으로 탐색하는 순차탐색, 비선형 구조를 전체적으로 탐색하는 DFS,BFS

이 연산을 수행하게 되면 시간 복잡도는 O(2^n)이 되어 굉장히 오래걸리게 된다.

 

접근법 2) Dynamic Programming

따라서 DP로 문제를 해결하여야 한다. DP를 사용할 수 있는 조건은 아래와 같다.

• 최적 부분 구조(Optimal substructure): 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결할 수 있다
• 중복되는 부분 문제(Overlapping subproblem): 동일한 작은 문제를 반복적으로 해결한다.

 

배낭 문제가 최대 이익을 구하는 문제이지만, 쪼개보면 두가지 선택지만 존재한다.

1. 물건을 넣는다.
2. 물건을 넣지 않는다.

 

최대 K까지 담을 수 있는 배낭에 W무게의 물건을 넣는다고 가정해보자

넣었을 경우는 배낭에 (K-W)무게를 더 넣을 수 있다.

넣지 않았을 경우에는 배낭에 여전히 K무게를 더 넣을 수 있다.

이 과정을 가방에 더이상 넣을 수 없을 때까지 모든 물건에 반복한다.

 

이는 W무게의 물건과 (K-W)무게까지 담을 수 있는 배낭으로 생각할 수 도 있다.

 

예를 들어

6kg까지 담을 수 있는 배낭이 있고 무조건 2kg 물건을 넣는다고 생각해보자.

그러면 그냥 4kg의 배낭으로 문제를 풀어도 되는 것이다.

 

4kg배낭에 3kg물건을 넣는다고 가정하면 1kg의 배낭문제가 된다.

 

최대 6kg을 담을 수 있는 배낭의 최대가치

=

2kg물건의 가치 + 최대 4kg을 담을 수있는 배낭의 가치

=

2kg물건의 가치 + 3kg물건의 가치 + 최대 1kg을 담을 수 있는 배낭의 가치

 

이런식으로 생각할 수있는것이다.

이게 위에서 말한대로 부분문제가 큰 문제가 되는 DP의 특징이다.

 

 

식으로 세워보면

dp에는 최대가치를 담는다.

dp[ i ][ j ]

i : 현재 물건의 번호

j : 최대 무게

 

최대가치를 담아야하기 때문에 값을 비교한다.

• 물건 i를 배낭에 담지 않는경우 dp[ i ][ j ] = dp[ i-1][ j ]
• 물건 i를 배낭에 담는 경우 dp[ i ][ j ] = dp[ i ][ j - i의 무게 ] + i의 가치

dp[ i ][ j ] = max(dp[ i-1 ][ j ], dp[ i ][ j - i의 무게 ] + i의 가치)

 

배낭문제의 시간 복잡도는 O(nK)이다. (n: 물건의 개수, K: 배낭의 최대 무게)

그런데 배낭의 용량인K가 물건의 개수n에 비해 너무 커지면, 시간이 너무 길어져 해를 찾기 어렵다.

따라서 배낭문제는 제한적인 입력 크기에 대해서만 효용성을 가진다.

 

 

풀이 )

현재 물건의 무게가 배낭의 최대 무게보다 많을 때에는 어차피 물건을 넣지 못하기 때문에

if문으로 nowWeight< weight일 경우를 따로 빼주었다.

N, K = map(int,input().split())
load = [[0,0]] + [list(map(int,input().split())) for _ in range(N)]
dp = [[0]*(K+1) for _ in range(N+1)]

for i in range(1,N+1):
    weight = load[i][0]
    value = load[i][1]
    
    for nowWeight in range(1,K+1) :
        if nowWeight < weight :
            dp[i][nowWeight] = max(dp[i-1][nowWeight], dp[i][nowWeight-1])
        else :
            dp[i][nowWeight] = max(value + dp[i-1][nowWeight-weight], dp[i-1][nowWeight])

print(dp[N][K])

 

 

 

 

 

 

📖 참고자료

[DP] 배낭 문제 (Knapsack Problem)

배낭 문제(KnapSack Problem) 그림으로 쉽게 이해하기