문제 풀이

배낭 문제(KnapSack Problem)

윤진노 2024. 1. 28. 23:33

백준 평범한 배낭 문제를 발견하고 도전을 하다가 이에 관한 문제들이 시리즈로 돼있는 것을 발견하고, 이것에 대해 정리를 해보고자 한다.

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

 

12865번: 평범한 배낭

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)

www.acmicpc.net

 

 

배낭 문제(KnapSack Problem)이란?

n개의 물건이 있을때, 각 물건에는 가치와 무게가 존재한다.

무게를 정해주고, 해당 무게를 넘어서는 배낭에 물건을 담지 못한다.

이 때, 가장 물건의 가치를 높게 배낭에 담는 문제이다.

 

 

해당 문제를 한번 살펴보자.

15kg까지 담을 수 있는 베낭에 물건들이 담겨 있다. 이때, 상자들은 선택하거나 안하거나 두가지 선택 경우의 수 밖에 없다는 것이다.

그렇다면 어떻게 가져가야 최대 가치를 창출해 낼 수 있을까? 고민을 해보자.

 

 

 

 

 

이 문제도 한번 살펴보자. 

15kg까지 담을 수 있는 베낭에 물건들이 담겨 있다. 이때 상자들은 여러가지 하위 상자로 나누어 쪼개질 수 있다.

원하는 만큼 퍼갈 수 있다는 것이다. 지금은 예시를 상자로 말해서 띠용스럽겠지만 이런걸 액체나 쉽게 나눌 수 있는 것으로 말하면 조금 더 문제에 납득이 갈 수 있을것이다.

어쨌든, 얼핏 보면 그냥 똑같이 풀면 될 것 같지만 이 전에 말했던 문제에서는 브루트 포스로 풀면(시간 복잡도가 2^n으로 매우 좋지 않을 거지만..) 풀리긴 풀리겠지만 이번의 경우에는 그렇게 풀기도 매우 어려워 보인다.

 

 

 

 

 

 

 

ㄴ2

분할 가능한 배낭 문제 vs 0-1 배낭 문제

 

위에서 말했던 예시들처럼 배낭 문제는 크게 두 가지로 나뉜다.

담을 물건들이 쪼개어 질 수 있으면 분할 가능한 배낭 문제 그렇지 않으면, 0-1 배낭 문제로 나뉜다.

두 문제는 푸는 방법이 완전히 다르니 한번 알아보자.

 

 

 

 

 

분할 가능한 배낭문제

분할 가능한 배낭문제는 0-1 배낭 문제보다 풀기가 훨씬 쉽다.

제약조건이 크게 없다. 내가 담고싶은거 부터 담고 마지막에 담길 것을 가져갈 수 있는 용량의 최대치에 맞게 잘라주면 된다.

 

이에, 이 문제는 무게 대비 가치(가치/무게)가 높은 순으로 담아주는 그리디(Greedy) 알고리즘을 적용시켜 주면 된다.

이를 파이썬 코드로 한번 살펴보자.

def knapsack(W, w, p):
    n = len(w) - 1
    K = [0] * (n + 1)
    weight = 0
    for i in range(1, n + 1):
        weight += w[i]
        K[i] = w[i]
        if (weight > W):
            K[i] -= (weight - W)
            break;
    return K

 

W = 배낭의 담을 수 있는 최대 무게

w = 물건의 무게가 담겨 있는 무게 배열

p = 물건의 가치가 담겨 있는 배열

 

문제마다 크게 다르진 않겠지만, 그리디 알고리즘인 것을 깨달으면 그만큼 쉬운게 없다고 생각하는게 그리디 알고리즘이다.

 

 

 

 

 

 

 

 

0 - 1 배낭 문제

이번에는 분할 가능한 배낭 문제와 다르게 쪼갤 수 없으므로, 얼핏 보면 그리디 알고리즘이 적용될 수 있을 것 같지만 적용이 되지 않는다.

이에, 이러한 문제들은 DP(동적 계획법)을 이용해서 해결할 수 있다.

 

 

문제에서 물건은 2가지의 행동을 취할 수 있다.

1. 담긴다 2. 담기지 않는다 이다. 

 

먼저, 10KG까지 담을 수 있는 배낭이 있다고 생각해보자. 그리고 여러가지 물건이 있는데 3Kg짜리 4$의 물건이 있다고 하자.

그리고 이 물건을 담았다고 치자. 그렇다면 남은 가방의 여유공간은 7KG이다.

 

이렇게 되면 7KG 담을 수 있는 배낭이 생긴것이고, 이는 또 하나의 문제로 잘게 쪼개어 진 것이다. 이렇게 큰 문제가 작은 문제로 쪼개어 지고 그 작은 문제의 답들이 모여서 큰 문제의 답이 된다. 이것은 곧 DP(동적계획법)의 발동조건으로 DP를 이용해서 쉽게 풀 수 있다.

 

포스팅에 올려둔 백준 문제는 이 0 -1 배낭 문제이다.

코드를 보자.

 

import sys

N, K = list(map(int, sys.stdin.readline().split()))
arr = [[]for _ in range(N+1)]
for i in range(1,N+1):
    W, V = list(map(int, sys.stdin.readline().split()))
    arr[i] = (W, V)

dp = [[0] * (K+1) for _ in range(N+1)]

for i in range(1,N+1):
    W,V = arr[i] # W = 무게, V = 가칭
    for j in range(1,K+1):
        if j < W :  dp[i][j] = dp[i-1][j]
        else: dp[i][j] = max(dp[i-1][j], V+dp[i-1][j-W])


print(dp[N][K])

 

여기서 dp배열을 2중 배열로 만들어서 bottom-up 의 동적 계획법으로 해결하였다.

dp[i][j]가 의미하는 것은 i번째 베낭 까지 고려하였을 때, j무게 일 때 가질 수 있는 최대 이익이다.

즉 배열 dp는 최대이익을 담는 배열이다.

 

dp[i][j] = max(dp[i-1][j], V+dp[i-1][j-W]

이러한 점화식을 구했으므로 dp를 이용하여 재귀함수를 이용한 Top-down으로 풀던, 나처럼 Bottom-Up으로 풀면 된다.


글에 솜씨가 없어서 설명을 정말 못했지만

그냥 내가 되돌아봤을 때, 한번 더 이랬었지~ 하며 생각할 수 있게 글로 남긴다...이만 총총