[백준] 12865. 평범한 배낭
문제
이 문제는 아주 평범한 배낭에 관한 문제이다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.
입력
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.
입력으로 주어지는 모든 수는 정수이다.
출력
한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.
예제 입력
1
2
3
4
5
4 7
6 13
4 8
3 6
5 12
예제 출력
1
14
풀이
이 문제는 순열이 아니라 조합 문제라고 생각됨 (확실하지 않음).
- 물건을 넣는 순서는 상관이 없으나 중복이 있어서는 안됨
순서가 상관이 없는 문제이기 때문에 섣부르게 아래와 같은 중첩 for문과 같은 방법을 사용해선 안됨.
1번 물건 -> 2, 3, 4번 물건
2번 물건 -> 1, 3, 4번 물건
3번 물건 -> 1, 2, 4번 물건
4번 물건 -> 1, 2, 3번 물건
위 방법대로 최대 가치를 확인한다면 물건을 보는 순서가 생겨버리기 때문에 문제가 발생할 수 있음.
예를들면 2번 물건을 넣는다고 했을 때, 처음에 1번 물건을 넣을 수 있어서 가방에 넣었는데
실제로는 1번 물건을 넣지않고 3, 4번 물건을 넣는 것이 최대 가치가 더 높을 수 있음.
이처럼 단순히 순서대로 보도록 하면 안되고 물건이 들어갈 수 있는 모든 케이스에서의 가치를 비교하여 최대 가치를 얻어내야만 하는 문제다.
자, 이제 어떤 접근방법을 써야할지 생각해보자..
이 문제의 목표는 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 구하는 것이다.
하나의 변수에 최대값을 계속해서 갱신해나갈수도 있겠지만, 최대 무게라는 제한이 있기 때문에
Dynamic Programming Table을 생성하여 무게별 최대가치를 갱신해나가는 방법이 좋아보인다.
코드로 작성하면 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 물품의 수 n, 최대 무게 k
n, k = map(int, input().split())
thing = [[0,0]]
knapsack = [[0]*(k+1) for _ in range(n+1)]
for i in range(n):
thing.append(list(map(int, input().split())))
for idx in range(1, n+1):
# idx는 물품의 index, notice) 1번부터 시작
weight = thing[idx][0]
value = thing[idx][1]
for wg in range(1, k+1):
# wg는 0부터 최대 무게까지 그때그때의 최대무게가 됨
if wg >= weight:
knapsack[idx][wg] = value + knapsack[idx-1][wg-weight]
knapsack[idx][wg] = max(knapsack[idx][wg], knapsack[idx-1][wg])
else:
knapsack[idx][wg] = knapsack[idx-1][wg]
print(knapsack[n][k])
2차원 DP Table을 만든다. DP Table의 row는 각 물품, col은 최대 무게이다.
아래쪽에 DP Table의 모든 요소를 지나가는 중첩 For문이 있다.
각 물건이 들어갔을 때의 최대 무게별 최대가치를 저장하면서 내려온다.
knapsack[idx][wg] = value + knapsack[idx-1][wg-weight]
이 부분은 value 현재 물건의 가치와
knapsack[idx-1][wg-weight], 즉 현재 물건의 무게를 최대 무게에서 뺀 -> 남은 무게에서의 최대 가치를 더하는 문장이다.
정리하면 knapsack[idx][wg] = value + knapsack[idx-1][wg-weight]은 wg가 최대 무게일 때, 최대 가치를 나타낸다.
그 아래에서는 max함수를 사용하여 이전의 최대가치와 현재의 최대가치를 비교하여 그중 더 높은 가치로 기록함으로써
무게별 최대가치를 계속해서 갱신해나가게 된다.
실패
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 물품의 수 n, 최대 무게 k
n, k = map(int, input().split())
thing = [[0,0]]
knapsack = [0]*(k+1)
for i in range(n):
thing.append(list(map(int, input().split())))
for idx in range(1, n+1):
# idx는 물품의 index, notice) 1번부터 시작
weight = thing[idx][0]
value = thing[idx][1]
for wg in range(1, k+1):
# wg는 0부터 최대 무게까지 그때그때의 최대무게가 됨
if wg >= weight:
knapsack[wg] = max(knapsack[wg], value + knapsack[wg-weight])
else:
knapsack[wg] = knapsack[wg]
print(knapsack[k])
이렇게 1차원 DP table로 만들어서도 해봤는데.. 이유는 모르겠지만 오답으로 처리된다..
위의 방법과 크게 다를것이 없어보이는데.. 이유를 알게되면 업데이트하도록 하겠다.