문제
https://www.acmicpc.net/problem/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))
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 12852. 1로 만들기 2 (0) | 2024.04.24 |
---|---|
[BOJ] 1463. 1로 만들기 (0) | 2024.04.21 |
[BOJ] 1026. 보물 (0) | 2024.04.21 |
[BOJ] 14501. 퇴사 (1) | 2024.04.06 |
[BOJ] 14502. 연구소 (0) | 2024.04.06 |