[Python] BOJ 12865 : 평범한 배낭

요구사항

1. 시간 제한 2초
   1. 2억번 연산이 가능 . N**2 어려울 듯, 그 이하 시간복잡도를 사용
2. 메모리 제한 512MB
   1. 리스트 안의 튜플 10,000개가 약 1.4MB 따라서 메모리 제한은 넣어둘것
3. 배낭에 들어갈 수 있는 무게를 초과하지 않는 선에서 가치가 가장 높은 최댓값을 출력

설계

1. 배낭의 무게보다 무거운 아이템은 제외
2. 가치, 무게 순서대로 내림차순 정렬 (+ 근데 내림차순을 동시에 하면서 하나는 더 큰 값으로 다른 하나는 더 작은 값으로 할 수 있나?)
3. 아이템 리스트를 순회하면서 각 원소를 꺼냄
4. 만약 배낭 무게가 <= 0 이라면 break
   1. <=0 으로 하려고 했는 데 예외가 있을 수도 
   2. 예를 들어 배낭의 무게가 3이고 아이템의 무게가 4라면
   3. elif 문에 안걸리게 된다. 
   4. 아니다... 그러다 끝나겠지  for문이니깐... 
5. 아니라면, 각 아이템 무게가 현재 배낭의 무게보다 작다면
   1. 배낭의 무게 -= 아이템의 무게
   2. 전체 가치 += 아이템의 가치 
6. return 전체 가치 

• 위 로직에 문제가 있다. 평범한 배낭 예제 입력을 보면 내 로직은 정렬한 뒤 0번 째 인덱스의 값을 넣고 끝이 나지만..
• 문제는 (4, 8) , (3, 6) 을 넣어 더 큰 가치를 창출해낸다. 
• 무게 순서로 해야되려나..
  • 근데 이것도 반례가 있다. 예를 들어서 문제의 예시로 예로 들면 현재 무게순으로 정렬하면 
  • (3, 6), (4, 8), (5, 12), (6, 13) 이기 때문에 만족하지만, 아래 반례를 쉽게 생각해볼 수 있다.
  • (3, 1), (4, 1), (5, 12), (6, 13) 이게 된다면 앞에서 차례로 넣어 배낭을 채워도 가장 큰 가치라고 볼 수는 없다. 
• 따라서 다른 접근 방식이 필요하다. 밑에 알고리즘 분류를 보았다. 동적계획법 문제로 분류되었다. 
• 아이템의 kg당 가치를 환산해서 정렬하고 빼는 건 큰 가치의 무게를 빼주면 ...?
  • 마찬가지로 반례가 존재한다. 
• 2차원 배열을 만들어 해결할 수 있다. 

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4	0	0	0	6	8	12	14	14

• 0 ~ 7 : 가방에 들어갈 수 있는 무게
• 0 ~ 4 : 아이템 목록 
• 각각을 0부터 시작하는 이유는 예외처리가 귀찮아서이다. 
• 각 아이템의 무게보다 작은 건 볼 필요없다. 
• 1, 2, 3, 4 아이템의 무게와 가치는 (6, 13) (4, 8) (3, 6) (5, 12) 이다. 
• 1번 아이템의 무게가 6이므로 6미만으로는 넣을 수도 없을 것이다. 그 뒤로는 1번 아이템의 가치인 13을 갖는다. 
• 2번 아이템의 무게는 4이고 가치는 8이다. 따라서 위 표와 같이 넣을 수 있을 것이다. 
  • 6kg 일 때
  • 이 때, 넣을 공간의 왼쪽과 (넣을 수 있는 무게 - 현재 아이템의 무게 + (더 넣을 수 있는 공간)을 더한다. 
  • 왼쪽 (8)과 (넣을 수 있는 무게 (6kg) - 현재 아이템의 무게(4kg)) -> 더 넣을 수 있는 공간 (2kg) = 0
  • + 현재 아이템의 가치 (8) 와 위에를 비교한다. 따라서 max(8, 13) 이니 13이 들어간다.
  • 만약에 2번 아이템과 1번 아이템의 순서가 변경됐다면, 왼쪽과 여러 가지 뺀걸 비교해야겠다.
  • 만약 일관성 있게 이런 유형을 다루고 암기하고 싶다면, 정렬을 하는 것도 방법일 수 있을 거 같다. 
• 위와 같이 모든 아이템들을 순회해서 비교해준다. 

설계

import sys
input = lambda: sys.stdin.readline().rstrip()

N, K = map(int, input().split())

items = [list(map(int, input().split())) for _ in range(N)]

def knapsack(items, K):
    M = len(items)
    dp = [[0] * (K + 1) for _ in range(M + 1)]

    for i in range(1, M + 1):
        for j in range(1, K + 1):  
            if j >= items[i - 1][0]:  
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - items[i - 1][0]] + items[i - 1][1])
            else:
                dp[i][j] = dp[i - 1][j]
                
    return dp[M][K] 

print(knapsack(items, K))

더 쉽게 푸는 법

def knapsack(items, K):
    dp = [0] * (K + 1)

    for weight, value in items:
        for j in range(K, weight - 1, -1):
            dp[j] = max(dp[j], dp[j - weight] + value)

    return dp[K]

import sys
input = lambda: sys.stdin.readline().strip()

N, K = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

print(knapsack(items, K))

• 역순으로 처리해주는 이유는 현재 아이템을 사용할 때, 이전의 dp배열을 수정하지 않기 위해서이다.

1 번째 질문에 대한 답변

백준에 나와 있는 예제 입력으로 테스트를 해볼 때는 역순으로 하지 않아도 되지만 분명히 반례는 존재합니다. 

우선 아래 소스 코드를 먼저 보시죠. 

def knapsack(items, K):
    dp = [0] * (K + 1)

    for weight, value in items:
        for j in range(weight, K+1):
            dp[j] = max(dp[j], dp[j - weight] + value)

    return dp[K]

import sys
input = lambda: sys.stdin.readline().strip()

N, K = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

print(knapsack(items, K))

• 위 소스 코드로 예제 입력을 넣었을 때는 의도한 결과값인 14가 나오게 됩니다. 하지만 반례가 존재하는 이유는 평범한 배낭 문제는 물건의 개수가 정해져 있고, 물건을 한번만 넣을 수 있는 데, 위 코드의 경우 물건을 여러 번 사용할 수 있는 방법으로 처리되고 있습니다. 예를 들어 무게가 작고 가치가 큰 경우 그 아이템을 반복해서 넣게 됩니다. 
• 예를 들어 아이템 = [(3, 10), (2, 100), (4, 5), (6, 1)] 이 있다면, K = 10
• 아이템 (3, 10) 처리 dp[j] = max(dp[j], dp[j - weight] + value)

- j = 3: dp[3] = max(dp[3], dp[3-3] + 10) = max(0, 0 + 10) = 10
- j = 4: dp[4] = max(dp[4], dp[4-3] + 10) = max(0, 0 + 10) = 10
- j = 5: dp[5] = max(dp[5], dp[5-3] + 10) = max(0, 0 + 10) = 10
- j = 6: dp[6] = max(dp[6], dp[6-3] + 10) = max(0, 10 + 10) = 20
- j = 7: dp[7] = max(dp[7], dp[7-3] + 10) = max(0, 10 + 10) = 20
- j = 8: dp[8] = max(dp[8], dp[8-3] + 10) = max(0, 10 + 10) = 20
- j = 9: dp[9] = max(dp[9], dp[9-3] + 10) = max(0, 20 + 10) = 30
- j = 10: dp[10] = max(dp[10], dp[10-3] + 10) = max(0, 20 + 10) = 30

 

DP 테이블 상태:

dp = [0, 0, 0, 10, 10, 10, 20, 20, 20, 30, 30]

• 아이템 (2, 100) 처리

- j = 2: dp[2] = max(dp[2], dp[2-2] + 100) = max(0, 0 + 100) = 100
- j = 3: dp[3] = max(dp[3], dp[3-2] + 100) = max(10, 0 + 100) = 100
- j = 4: dp[4] = max(dp[4], dp[4-2] + 100) = max(10, 100 + 100) = 200
- j = 5: dp[5] = max(dp[5], dp[5-2] + 100) = max(10, 100 + 100) = 200
- j = 6: dp[6] = max(dp[6], dp[6-2] + 100) = max(20, 200 + 100) = 300
- j = 7: dp[7] = max(dp[7], dp[7-2] + 100) = max(20, 200 + 100) = 300
- j = 8: dp[8] = max(dp[8], dp[8-2] + 100) = max(20, 300 + 100) = 400
- j = 9: dp[9] = max(dp[9], dp[9-2] + 100) = max(30, 300 + 100) = 400
- j = 10: dp[10] = max(dp[10], dp[10-2] + 100) = max(30, 400 + 100) = 500

 

DP 테이블 상태:

dp = [0, 0, 100, 100, 200, 200, 300, 300, 400, 400, 500]

• 아이템 (4, 5)

- j = 4: dp[4] = max(dp[4], dp[4-4] + 5) = max(200, 0 + 5) = 200
- j = 5: dp[5] = max(dp[5], dp[5-4] + 5) = max(200, 0 + 5) = 200
- j = 6: dp[6] = max(dp[6], dp[6-4] + 5) = max(300, 100 + 5) = 300
- j = 7: dp[7] = max(dp[7], dp[7-4] + 5) = max(300, 100 + 5) = 300
- j = 8: dp[8] = max(dp[8], dp[8-4] + 5) = max(400, 200 + 5) = 400
- j = 9: dp[9] = max(dp[9], dp[9-4] + 5) = max(400, 200 + 5) = 400
- j = 10: dp[10] = max(dp[10], dp[10-4] + 5) = max(500, 300 + 5) = 500

 

DP 테이블 상태:

dp = [0, 0, 100, 100, 200, 200, 300, 300, 400, 400, 500]

• 아이템 (6, 1)

dp = [0, 0, 100, 100, 200, 200, 300, 300, 400, 400, 500]

 

따라서 가장 큰 가치는 500이 나오게 됩니다. 

 

아래 사진은 역순으로 하지 않았을 때, 직접 인터프리터가 되어 그 과정을 보여줍니다. 

 

그래도 이해가 잘 안되시면 댓글 주세요.