[BOJ] 12865. 평범한 배낭

문제

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

12865번: 평범한 배낭

 

개인적으로 좀 어려웠던 문제..

 

---

 

주요 아이디어

처음 생각했던 방법은, 가치 기준 내림차순 & 같은 가치일 경우 무게 기준 오름차순 한 다음 for문을 돌면서 하나씩 더해주며 최대값을 찾는 방법이었다.

 

---

 

코드 구현 (Python 3)

 

n, k = map(int, input().split())
items = []

for _ in range(n):
    w, v = map(int, input().split())
    if w <= k:
        items.append((w, v))

items.sort(key=lambda x: (-x[1], x[0]))

# 리스트 순회하면서 어떤게 최대값인지 찾기
max_value = 0

for i in range(len(items)):
    cur_weight, cur_value = items[i]
    # print('cur :', cur_weight, ',', cur_value)

    for ni in range(i+1, len(items)):
        if cur_weight + items[ni][0] <= k:
            # print('add ', items[ni][0], ',', items[ni][1])
            cur_weight += items[ni][0]
            cur_value += items[ni][1]

    if cur_value > max_value:
        max_value = cur_value

print(max_value)

 

 

결과는 실패...

 

---

실패 원인

인터넷과 질의응답 페이지에 있는 대부분의 반례를 넣어보았으나 정확한 반례를 찾지는 못했다.

다만 확실한건 K, W가 100,000 이 최대값이기 때문에 이중 for문으로 풀이를 시도할 경우 시간 복잡도가 O(n^2) 이 되어 애초에 좋은 풀이가 아니라는 것이다.

 

---

따라서 아래 2가지 자료를 참고해, 각각의 풀이 방식을 알아보았다.

 

1. 1차원 DP 활용 방식

https://www.youtube.com/watch?v=uggO0uzGboY

테스트 케이스를 예시로 들어보자.

4 7
6 13
4 8
3 6
5 12

물품의 수는 4개, 준서가 버틸 수 있는 무게는 7이 되고 각 물건의 무게와 가치는 다음과 같다.

	무게 (W)	가치 (V)
A	6	13
B	4	8
C	3	6
D	5	12

 

각 물건을 넣었을 경우의 최대 가치를 table로 나타내보자.

1. items = [A]

w	A
0	0
1	0
2	0
3	0
4	0
5	0
6	13
7	0

 

물건의 종류가 A 하나이므로 weight = 6, value = 13이 되는 경우만 채워준다.

 

2. items = [A, B]

w	A	B
0	0	0
1	0	0
2	0	0
3	0	0
4	0	8
5	0	0
6	13	13
7	0	0

 

A와 B를 모두 넣는 경우에는 최대 무게인 7을 초과하므로 고려하지 않고, B를 넣었을 때의 경우만 추가해준다.

 

3. items = [A, B, C]

w	A	B	C
0	0	0	0
1	0	0	0
2	0	0	0
3	0	0	6
4	0	8	8
5	0	0	0
6	13	13	13
7	0	0	14

A+C > K이므로 고려하지 않고, B+C = 7이므로 해당 자리에 추가해준다.

 

4. items = [A, B, C, D]

w	A	B	C	D
0	0	0	0	0
1	0	0	0	0
2	0	0	0	0
3	0	0	6	6
4	0	8	8	8
5	0	0	0	12
6	13	13	13	13
7	0	0	14	14

A+D, B+D, C+D 모두 7을 초과하므로 고려하지 않는다.

 

최종적으로 table은 아래와 같고, 마지막 item인 D의 column 중 최대값을 찾으면 그게 정답이 된다.

w	A	B	C	D
0	0	0	0	0
1	0	0	0	0
2	0	0	0	0
3	0	0	6	6
4	0	8	8	8
5	0	0	0	12
6	13	13	13	13
7	0	0	14	14

 

점화식으로 표현하면 다음과 같다.

-> (기존에 있던 값, 새롭게 value를 더해준 값)

\(table[i][j+w[i]] = max(table[i-1][j+w[i]], table[i-1][j] + v[i])\)

n, k = [int(x) for x in input().split()]
table = [0] * (k+1)

for _ in range(n):
    w, v = [int(x) for x in input().split()]
    if w > k:
        continue
    for j in range(k, 0, -1):
        if j + w <= k and table[j] != 0:
            table[j+w] = max(table[j+w], table[j]+v)
    
    table[w] = max(table[w], v)

print(max(table))

 

 

---

 

제출 결과

 

2. 2차원 DP 활용 방식

https://hongcoding.tistory.com/50

1. x축에는 가방 1~K까지의 무게, y축은 물건 N개 만큼의 2차원 배열 만들어주기

 

	0	1	2	3	4	5	6	7
A (w=6, v=13)	0	0	0	0	0	0	13	13
B  (w=4, v=8)	0	0	0	0	8	0	13	13
C  (w=3, v=6)	0	0	0	6	8	0	13	14
D   (w=5, v=12)	0	0	0	6	8	12	13	14

 

현재 배낭의 허용 무게보다 넣을 물건의 무게가 더 크다면 넣지 않는다.

그렇지 않다면, 다음 2개 중 더 큰 가치를 선택해서 넣는다.

a. 현재 넣을 물건의 무게만큼 배낭에서 빼고 현재 물건 넣기

b. 이전 배낭 그대로 가지고 가기

 

N, K = map(int, input().split())
# 최대 K만큼의 무게로 가치 합의 최대값을 출력

from itertools import combinations

def solution(N, K):
    dp_list = [[0 for _ in range(K+1)] for _ in range(N+1)]
    item_list = [[0,0]]

    for _ in range(N):
        item_list.append(list(map(int, input().split())))
    

    for i in range(1, N+1):
        for j in range(1, K+1):
            weight = item_list[i][0]; value = item_list[i][1]

            # 현재 물건이 들고 있는 무게보다 작다면
            if j < weight:
                dp_list[i][j] = dp_list[i-1][j] # 위의 값을 그대로 가져오기
            
            else:
                dp_list[i][j] = max(value + dp_list[i-1][j-weight], dp_list[i-1][j])

    return dp_list[N][K]

print(solution(N, K))