[백준][12865번] 평범한 배낭

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

 

 

 

 

내 생각

 

대충 문제 흐름으로 반복문을 통해 배낭에 넣을 수 있는 최대 가치를 구해야겠다는 생각을 하였다.

→ Knapsack Problem 문제! 

1. 입력 : 물건의 수(N), 배낭의 무게 제한(K), 각 물건의 무게(W), 각 물건의 가치(V)

2. 반복문으로 각 상태에 대한 최대 가치 저장 : 2차원 다이나믹 프로그래밍(dp) 배열
- 현재 물건을 배낭에 넣을 수 없다 ?  →  [이전 물건][같은 무게](dp[i-1][j]) : i번째 물건 안넣어
- 있다?  →  i번째 물건을 넣지 않고 j의 무게를 만드는 경우와 i번째 물건을 넣고 j의 무게를 만드는 경우 중에 더 가치가 높은 것을 선택 : dp[i][j] =max(dp[이전 물건][현재 가방 무게], dp[이전 물건][현재 가방 무게 - 현재 물건 무게] + 현재 물건 가치 )

 

 

 

 

내 코드

 

# 1. 입력 처리
# 입력으로 물건의 수 N, 배낭의 무게 제한 K, 각 물건의 무게(weights), 각 물건의 가치(values)
N, K = map(int, input().split())
weights = []
values = []
for _ in range(N):
    w, v = map(int, input().split())
    weights.append(w)
    values.append(v)

# 3. 다이내믹 프로그래밍 배열 초기화
# dp[i][j]: 배낭에 넣은 물건 중 무게가 j일 때의 최대 가치를 저장하는 배열
dp = [[0] * (K + 1) for _ in range(N + 1)]

# 4. 다이내믹 프로그래밍 : 중첩된 반복문을 사용하여 각 상태에 대한 최대 가치를 계산
for i in range(1, N + 1):
    for j in range(1, K + 1):
        if weights[i - 1] <= j: #현재 물건을 넣을 수 있는 경우
			 # 현재 물건을 넣지 않은 경우와 넣은 경우 중 더 가치가 큰 값을 선택하여 저장
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
        else: 
        	# 현재 물건을 넣을 수 없는 경우, 이전 상태의 값을 그대로 가져옴
            dp[i][j] = dp[i - 1][j] 

result = dp[N][K]
print(result)

 

 

 

 

** 다이나믹 프로그래밍(동적 계획법, dp)
    : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. (wikipedia)

• 부분 반복 문제(Overlapping Subproblem) : 재귀
• 최적 부분 구조(Optimal Substructure) : 작은 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답

** 메모이제이션(Memoization)
    : 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다. (wikipedia)