[크래프톤 정글] 백준 12865번 평범한 배낭 문제

배낭 문제 는 동적 계획법(DP) 문제의 대표적인 예로, 주어진 아이템을 배낭에 담아 최대 가치를 구하는 문제다. 이걸 이하는데 시간이 매우 오래 걸렸지만 아직도 dp의 접근 방식과 , 점화식을 세우는건 좀 부족하다. 그래도 이해 한 만큼 에 대해서는 정리를 해보고자 한다.

1. 문제 정의

• 주어진 무게 제한 k가 있는 배낭에 n개의 아이템을 넣으려고 한다.
• 각 아이템 i는 무게 v[i]와 가치 w[i]를 가지고 있다.
• 목표는, 무게 제한을 넘지 않으면서 배낭에 담을 수 있는 아이템들의 가치 합을 최대화하는 것이다.

2. 문제의 특징

• 각 아이템은 한 번만 선택할 수 있다. 즉, 선택하거나 선택하지 않는 두 가지 선택지뿐이다. (0/1 문제)
• 선택을 할 때, 배낭의 용량을 넘지 않도록 해야 한다.
• 목표는 최대 가치를 얻는 것이다.

3. 동적 계획법(DP)으로 해결하기

이 문제는 DP로 접근할 수 있는데, DP의 핵심은 부분 문제를 정의하고, 이를 이용해 전체 문제를 해결하는 것이다.

3.1. 부분 문제 정의

• dp[i][j]를 정의한다. 여기서 dp[i][j]는 i번째 아이템까지 고려했을 때, 배낭의 용량이 j인 상태에서 얻을 수 있는 최대 가치를 의미한다.
  • i: 현재 고려하는 아이템의 인덱스
  • j: 배낭의 현재 용량

3.2. 상태 전이(State Transition)

각 아이템을 선택할 때, 두 가지 선택지가 있다:

1. i번째 아이템을 배낭에 넣지 않는다:

   • 이 경우, 이전 상태와 동일하게 dp[i-1][j] 값을 그대로 가져온다.
   • 즉, i번째 아이템을 고려하지 않고 배낭의 용량 j에서 얻을 수 있는 최대 가치를 유지한다.
   • 수식: dp[i][j] = dp[i-1][j]

2. i번째 아이템을 배낭에 넣는다:

   • 이 경우, i번째 아이템의 무게를 고려해 남은 배낭의 용량 j - v[i]에서 얻을 수 있는 최대 가치에 i번째 아이템의 가치를 더해야 한다.
   • 즉, i번째 아이템을 넣고 남은 용량에서 최적의 해를 구해 현재 아이템의 가치를 더한다.
   • 수식: dp[i][j] = dp[i-1][j - v[i]] + w[i] (단, j >= v[i]일 때만 가능)

3.3. 상태 전이 수식

따라서, 두 가지 선택 중 더 나은(가치가 큰) 것을 선택한다. 즉:

dp[i][j] = max(dp[i-1][j], dp[i-1][j - v[i]] + w[i])  # 단, j >= v[i]일 때만

• dp[i-1][j]: i번째 아이템을 넣지 않았을 때의 최대 가치.
• dp[i-1][j - v[i]] + w[i]: i번째 아이템을 넣었을 때 남은 용량에서 얻을 수 있는 최대 가치와 현재 아이템의 가치를 더한 값.

4. 초기 조건 및 테이블 구성

• 초기화:

  • dp[0][j] = 0 (아무 아이템도 고려하지 않았을 때 배낭의 용량 j에서의 최대 가치는 0이다.)
  • dp[i][0] = 0 (배낭의 용량이 0일 때, 어떤 아이템도 넣을 수 없으므로 최대 가치는 0이다.)

• 테이블 채우기:

  • 위에서 설명한 상태 전이 식에 따라 2차원 DP 테이블을 채워나간다.
  • 마지막에 dp[n][k]가 배낭의 최대 용량 k에서 얻을 수 있는 최대 가치를 나타낸다.

5. 시간 복잡도

• 이 문제의 시간 복잡도는 O(n * k)이다.
  • n: 아이템의 개수.
  • k: 배낭의 용량.
  • 각 아이템마다 배낭의 용량만큼 반복문을 돌기 때문에, 이중 반복문을 사용해 테이블을 채운다.

6. 코드 구현

def find_max_weight(v ,w ,k) :

    for i in range(1, len(v)) :
        print("행 :" + str(i))
        for j in range(1, k+1) :
            if j >= v[i]:
                print("열 :" + str(j))
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])

            else :
                print("else 열  :" + str(j))
                dp [i][j] = dp[i-1][j]
                print("else dp:" + str(dp[i][j]))

    print(dp[-1][-1])



n,k = map(int, input().split())
dp = [[0] * (k + 1) for _ in range(n + 1)]
v = [0] * (n + 1)  # n+1 크기의 리스트로 초기화 (인덱스 1부터 사용)
w = [0] * (n + 1)

for i in range(1, n + 1):
    x, y = map(int, input().split())
    v[i] = x
    w[i] = y

find_max_weight(v,w,k)

7. 문제 접근 요령

0/1 배낭 문제에 접근할 때는 다음과 같이 생각해 볼 수 있다.

1. 부분 문제 정의: 문제를 더 작은 단위로 쪼개어 생각한다. 배낭의 용량과 넣을 아이템의 개수를 줄여가면서 최대 가치를 계산한다.
2. 상태 전이: 아이템을 넣는 경우와 넣지 않는 경우의 두 가지 상태 전이를 구체화하고, 이를 기반으로 DP 테이블을 채워나간다.
3. 테이블 초기화: 문제의 시작점, 즉 배낭이 비어 있거나 아이템이 없는 경우를 고려해 테이블을 초기화한다.
4. 결과 추출: DP 테이블에서 마지막 값(dp[n][k])이 최종적인 해를 나타낸다.

8. 확장 및 변형 문제

• 부분 배낭 문제(Fractional Knapsack Problem): 아이템을 쪼개서 넣을 수 있는 경우. 그리디 알고리즘으로 해결.
• 다차원 배낭 문제: 여러 개의 배낭이 있을 때 최대 가치를 구하는 문제.
• 다중 선택 배낭 문제: 각 종류의 아이템에서 하나만 선택해야 하는 문제.

결론

• 포함/미포함 전략: 배낭 문제에서의 핵심은 아이템을 넣을지 말지를 결정하는 것이다. 이때, 포함하는 경우와 포함하지 않는 경우를 나눠 생각하고, 그중 더 유리한 선택을 한다.
• 최적 해 선택: DP는 각 상태에서 최적의 선택을 기록해 나가는 방식으로 최종적으로 문제의 최적 해를 구한다.