•
문제
이 문제는 아주 평범한 배낭에 관한 문제이다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.
풀이
•
기본 알고리즘
1. 배낭 무게를 1 ~ i ~ k 로 최대치까지 늘려간다.
2. 배낭 무게가 i인 경우에 1 ~ j ~ n 번째 물건을 담을 수 있는지 체크한다.
3. 만약 j번째 물건을 담을 수 있는 경우에는 j번째 물건을 담은것과 담지 않는것의 가치를 비교한다.
!! 문장상으로는 담으면 무조건 좋은것처럼 보이지만 dp 배열에는 j-1번째까지의 물건을
담았을 때의 가치의 최대값이 이미 저장되어 있으므로 담지 않는것이 좋을수도 있음!
Python
복사
•
dp 동작
2차원 배열의 동작 구조는 i 번째 물건을 가지고 배낭의 무게를 1 ~ k 까지 늘려가면서 비교해준다.
즉 2차원 배열에서 위에서 아래로 내려오면서 행을 하나하나 비교해주는 형태가 된다.
이 상황에서 i 번째 물건을 비교하는 상황에서는 dp[i - 1][j]에 이미 i - 1 번째 물건을 넣는 경우까지의 최대값이 저장되어 있다. 따라서 배낭에 물건을 넣을 수 있는 경우에는 Max(해당 물건이 들어가기 전 배낭 무게의 가치에 새로운 물건에 가치를 더한 값 , i - 1 번째까지의 경우)로 계산할 수 있다.
만약 배낭에 물건을 넣지 못하는 경우에는 그냥 i - 1 번째까지의 값을 그대로 가져온다.
for i in range(n): # i 번째 물건
wei = weight[i][0] # 현재 비교해야 할 물건의 무게와 가치
val = weight[i][1]
for j in range(1, k + 1): # 배낭 무게가 j 일 때
if j >= wei:
dp[i][j] = max(dp[i-1][j - wei] + val , dp[i-1][j]) #
else:
dp[i][j] = dp[i-1][j]
Python
복사
•
전체 코드
n , k= map(int, input().split()) # 물품의 수, 버틸 수 있는 무게
dp = [[0] * (k + 1) for row in range(n)]
weight = [0] * (k + 1)
result = 0
for i in range(n):
w, v = map(int, input().split()) # 물품 무게, 가치
weight[i] = (w, v)
for i in range(n): # 물건
wei = weight[i][0]
val = weight[i][1]
for j in range(1, k + 1): # 배낭 무게
if j >= wei:
dp[i][j] = max(dp[i-1][j - wei] + val , dp[i-1][j])
else:
dp[i][j] = dp[i-1][j]
print(dp[n-1][k])
Python
복사
최적화 코드
•
2차원 배열에서 좌 → 우로 진행하는 가로형 dp 구현이 아닌 상 → 하로 진행하는 세로형 dp를 구현하는 경우에는 특정 물건에 대해 dp 를 모두 계산하고 다음 물건으로 진행하므로 물품들의 정보를 저장해줄 필요가 없다.
n, k = map(int, input().split())
dp = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
weight, value = map(int, input().split())
for j in range(1, k + 1):
if j < weight:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value)
print(dp[n][k])
Python
복사
중요
1.
C++ 에서는 행의 개수만큼의 벡터에 열의 개수만큼의 벡터를 삽입하여 2차원 벡터를 선언하지만, 파이썬에서는 행 렬의 위치가 반대이다. 바깥쪽 for문의 row가 행의 위치이다.
arr[n][k+1] 을 선언하기 위해서는 아래와 같이 초기화를 해야한다.
dp = [[0] * (k + 1) for row in range(n)]
Python
복사
