[다이나믹 프로그래밍] ★★ 12865번 - 평범한 배낭(22.05.15 복습완료)

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

(한줄평) 냅색 문제인지 모르고 풀었던... 생각보다 더 어려웠던 문제로 복습이 꼭 필요하다!!!

물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. N개의 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 구하는 문제다. 이 문제는 전형적인 냅색 문제다.

 

<냅색 알고리즘>

1. 분할가능 배낭 문제(Fractional Knapsack Problem)

담을 수 있는 물건이 나누어질 때(설탕 몇 g)

- 물건의 가격을 무게로 나누어 무게 대비 가격이 비싼 순서로 물건을 정렬해서 넣으면 쉽게 해결이 가능!

- 배낭이 감당할 수 있는 무게보다 물건의 무게가 많이 나가면 잘라서 넣는 방식

→ greedy로 해결 가능

 

2. 0-1 배낭 문제(0-1Knapsack Problem)

담을 수 있는 물건이 나누어질 수 없을 때(담는다 or 담지않는다)

- 물건을 자를 수 없으므로 물건의 무게, 가격, 배낭의 남은 용량을 모두 고려해야 한다..!

→ dp로 해결 가능

 

[참고] https://claude-u.tistory.com/208

#159 백준 파이썬 [12865] 평범한 배낭 - 냅색 알고리즘

[참고] https://velog.io/@uoayop/%EB%83%85%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

냅색 알고리즘

(풀이1) dp 테이블을 2차원 테이블로 생성

풀이 시간: 90분 이내

1) 문제 해결 아이디어

dp 테이블을 x축엔 가방 1~k까지 무게, y축은 물건 1~n개 로 하여 2차원 리스트로 생성한다.

예제 입력으로 들어온 값으로 생성했을 떄 예시다.

 

<경우의 수>

1. 현재 물건의 무게(w)가 가방 수용 가능 무게(j)보다 작거나 같은 경우

현재 물건을 가방에 담을지 말지 선택해야 함

현재 물건을 담았을 때 가치와 현재 물건을 담지 않았을 떄(이전 물건까지 가치의 최대합) 의 가치 중 더 큰 값으로 저장

2. 현재 물건의 무게(w)가 가방 수용 가능 무게(j)보다 큰 경우

현재 물건을 가방에 담지 못함

이전 물건까지 가치의 최대합을 그대로 저장

 

<점화식>

2) 소스코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())  # 물품 수, 배낭 수용 무게
# n개의 물건[무게, 가치]
graph = [list(map(int, input().split())) for _ in range(N)]
# d[i][j] : i번째 물건까, 배낭 수용 가능 무게가 j일때, 누적 가치
d = [[0] * (K + 1) for _ in range(N + 1)]   # (N+1)*(K+1)

# 가방에 담을 수 있는 물건(1~N) 반복
for i in range(1, N + 1):
  w, v = graph[i - 1]  # 현재 물건의 무게, 가치
  # 가방의 수용 가능 무게(1~K) 반복
  for j in range(1, K + 1):
    # 1. 현재 물건을 배낭에 넣는 경우, 누적 가치 계산
    # 현재 물건 무게 <= 현재 배낭 수용 무게
    if(w <= j):
      d[i][j] = max(d[i - 1][j - w] + v, d[i-1][j])
    # 2. 현재 물건을 배낭에 넣지 않는 경우, 누적 가치 계산
    # 현재 물건 무게 > 현재 배낭 수용 무게
    else:
      d[i][j] = d[i-1][j]

print(d[N][K])  # 물건 N개, 배낭최대수용무게가 K일 때 선택할 수 있는 물건 가치합의 최댓값

 

(풀이2) dp 테이블을 1차원 테이블로 생성(추천!)

풀이 시간: 40분 이내

1) 문제 해결 아이디어

dp 테이블을 x축엔 가방 수용 무게(1~k)로 하여 1차원 리스트로 생성한다.

여기서 중요한 점은 값을 덮어쓸 때 기존처럼 1열->K열 순서로 계산해도 되는가이다. 결론부터 말하면 안된다.

 

Q. 앞에서부터 값을 갱신하면 안되는 이유는?

앞에서부터 차례로 값을 갱신하면, 원래 활용해야하는 값이 아닌 이미 갱신된 값을 활용하는 문제가 발생한다. 맨 마지막 열부터 첫번째 열까지 역순으로 값을 덮어써야 한다!!

 

Q. 1차원 리스트를 사용할 수 있는 이유는?

위에서 보면 알겠지만 d[i][j] 값을 계산할 때는 이전 행(d[i-1])의 값만 알면된다.

이전 행 1개의 행만 알면될 때는 굳이 2차원 리스트를 사용할 필요가 없고 1차원 리스트로 값을 덮어쓰면 된다!!

 

<경우의 수>

1. 현재 물건의 무게(w)가 가방 수용 가능 무게(j)보다 작거나 같은 경우

현재 물건을 가방에 담을지 말지 선택해야 함

현재 물건을 담았을 때 가치와 현재 물건을 담지 않았을 때(이전 물건까지 가치의 최대합) 의 가치 중 더 큰 값으로 저장 -> 최댓값을 갱신해야함

2. 현재 물건의 무게(w)가 가방 수용 가능 무게(j)보다 큰 경우

현재 물건을 가방에 담지 못함

이전 물건까지 가치의 최대합을 그대로 저장 -> 갱신할 필요X

 

<점화식>

2) 소스코드

2-1) 덮어쓰기(추천)

import sys
input = sys.stdin.readline

N, K = map(int, input().split())  # 물품 수, 배낭 수용 무게
# n개의 물건[무게, 가치]
graph = [list(map(int, input().split())) for _ in range(N)]
# d[i] : 배낭 수용 가능 무게가 i일때, 누적 가치
d = [0] * (K + 1)

# 가방에 담을 수 있는 물건(1~N) 반복
for i in range(N):
  w, v = graph[i]  # 현재 물건의 무게, 가치
  # 가방의 수용 가능 무게(K~1) 반복
  for j in range(K, 0, -1):
    # 현재 물건을 넣는 경우, 넣지않는 경우 중 최댓값을 선택해 갱신
    # 현재 물건 무게 <= 현재 배낭 수용 무게
    if(w <= j):
      d[j] = max(d[j-w] + v, d[j])      
    # 현재 물건 무게 > 현재 배낭 수용 무게 이면 갱신X, 원래값 사용
  #print(d)
print(d[K])  # 물건 N개, 배낭최대수용무게가 K일 때 선택할 수 있는 물건 가치합의 최댓값

 

2-2) 다른 1차원 리스트에 값을 기록해두고 기록이 완료되면 원래 dp테이블에 갱신

import sys
input = sys.stdin.readline

N, K = map(int, input().split())  # 물품 수, 배낭 수용 무게
# n개의 물건[무게, 가치]
graph = [list(map(int, input().split())) for _ in range(N)]
# d[i] : 배낭 수용 가능 무게가 i일때, 누적 가치
d = [0] * (K + 1)

# 가방에 담을 수 있는 물건(1~N) 반복
for i in range(N):
  tmp = [0] * (K + 1)
  w, v = graph[i]  # 현재 물건의 무게, 가치
  # 가방의 수용 가능 무게(1~K) 반복
  for j in range(1, K+1):
    # 1. 현재 물건을 배낭에 넣는 경우, 누적 가치 계산
    # 현재 물건 무게 <= 현재 배낭 수용 무게
    if(w <= j):
      tmp[j] = max(d[j-w] + v, d[j])      
    # 2. 현재 물건을 배낭에 넣지 않는 경우, 누적 가치 계산
    # 현재 물건 무게 > 현재 배낭 수용 무게
    else:
      tmp[j] = d[j]
  d = tmp
  #print(d)
print(d[K])  # 물건 N개, 배낭최대수용무게가 K일 때 선택할 수 있는 물건 가치합의 최댓값

 

[참고] https://up-to-date-items.tistory.com/117

백준 12865번 1차원 리스트 풀이(파이썬)