백준 #12865.평범한배낭: DP,0-1Knapsap / 골드5

문제 링크 : https://www.acmicpc.net/problem/12865

🔍 Inspection

문제 접근(문제 분석 → 풀이 아이디어)

문제 요약

• N개의 물건들은 각각 무게 W 와 가치 V 을 가진다.

• 최대 K 만큼 무게를 넣을 수 있는 배낭에 넣을 수 있는 물건의 최대 가치값 을 구하라

• 입력 :

  1≤물품수 N ≤100 , 1≤배낭 무게제한 K≤100,000 , 1≤각 물건의 무게w≤ 100,000, 0≤ 각 물건의 가치 v≤1,000

유형 : 0-1 knapsap problem 을 위한 DP 사용

• DP[k][i]: 최대 K kg 제한을 가진 가방 안에 0~ i번쨰 item 까지 탐색 후 최대 가치

1. 물건 w > 배낭 무게제한 k :

   dp[k][i] = dp[k][i-1]

   1. 물건i는 못 넣음 → 이전i-1 최대 가치 유지

2. 물건 w <= 배낭 무게제한 k :

   dp[k][i] = max(item[v] + dp[k-w][i-1],dp[k][i-1])

   1. 물건i를 넣거나

      → 배낭 최대 무게 {k}-{item 무게} 만큼의 최대 가치 + 물건 i 의 가치 )

   ii. 안 넣거나

   → 이전i-1 최대 가치 유지 *(a)와 동일

🚩 FLOW

코드를 풀이할 때 적었던 플로우가 있나요?

1. 입력 변수 입력받기

• 물품 총 개수 / 제한 무게 / 물건별 무게 w, 가치 v

1. DP 정의

   • 최대가치 DP[k][i]: 최대 K kg 제한을 가진 가방안에 0~ i번쨰 item 까지 탐색 후 최대 가치

2. 배낭의 제한 무게를 0~K 씩 , 물건의 탐색 범위 0~N로 반복하여 DP 점화식 계산하기

   1. 물건 w > 배낭 무게제한 k : 물건 i는 배낭에 못 넣을 때 최대가치

      dp[k][i] = dp[k][i-1]

   2. 물건 w <= 배낭 무게제한 k : MAX(물건 i를 넣을 때 , 물건 i를 안 넣을 때)

      dp[k][i] = max(item[v] + dp[k-w][i-1],dp[k][i-1])

3. 최종 배낭 제한이 K 일때, 최대 가치 출력 = dp[K][N]