8일차 배낭 DP

들어가면서

매일 하겠다고 스스로 다짐했지만...
쉽지 않았다!!
하지만 그냥 또 도전하면 된다 !! 생각해보면 다시 시작하는게 제일 쉬움 
오ㅔ?!?!?!

그냥 하면 되기 때문 

배낭 DP

• 핵심개념 : 제한된 용량이 있는 배낭에 담을 물건을 골라 가치의 합을 최대로 만드는 문제
  각 물건의 개수에 따라서 문제의 유형이 나뉜다.

• 배낭 문제 유형 :

1. 0-1 Knapsack: 각 물건은 넣거나 안 넣거나 두 가지 선택만 있음 (쪼갤 수 없음)

2. `Unbounded Knapsack` : 무한 배낭 문제로 각 물건을 여러번 담을 수 있음. 

0-1 Knapsack (0-1 배낭 문제)

• 특징: 각 물건은 최대 1번만 담을 수 있음

• 점화식: 해당 무게 넣고, 가능한만큼 넣었을때 배낭의 가치(dp[i-1][w - weight[i]]) 의 합과, 해당 무게를 안넣었을때, 직전의 최댓값

  i : 아이템 번호
  w : 배낭의 현재 셋팅 무게 (점점 늘려가면서) 
  
  dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])

  • dp[i][w]: i번째 물건까지 고려, 용량 w일 때 최대 가치
  • "안 담는다 vs 담는다" 중 큰 값 선택

배열 최적화

• 2차원 → 1차원 배열 dp[w]로 압축 가능
• 단, 같은 물건을 여러 번 쓰지 않으려면 뒤에서 앞으로 순회해야 함

  for i in range(n):
      for w in range(capacity, weight[i]-1, -1):
          dp[w] = max(dp[w], dp[w-weight[i]] + value[i])

---

Unbounded Knapsack (무한 배낭 문제)

• 특징: 각 물건을 여러 번 사용할 수 있음 (제한 없음)

• 배낭 무게 제한은 여전히 있음

• 점화식:

  dp[i][w] = max(dp[i-1][w], dp[i][w - weight[i]] + value[i]) 
  # -> 여전히 아이템 i를 고려하는 상황
  

• 차이점: dp[i][...]를 참조 → 같은 아이템 반복 사용 가능

왜 무한 배낭 문제는 dp[i][w] 를 dp[i][w - weight[i]] + value[i], dp[i-1][w] 에서 고민할까?

무한 배낭 문제는 현재의 가치,무게를 가진 물건을 여러번 넣을 수 있다.

(1) dp[i][w - weight[i]] : s는 지금 물건을 여러번 넣을 수 있는 상황에서 새로 업데이트한 최댓값
(2) dp[i-1][w] : 아예 i번째 물건을 쓰지 않고 구한 최대 가치

내가 헷갈린 점; 그러면 dp[i][w - weight[i]] 는 i-1번째 물건은 아예 안넣은 최댓값인가?
아니다. dp[i][w - weight[i]] 값 또한 i-1번재까지 넣은 물건과 i번째 물건을 넣은 상태를 같이 고민해서 나온 최댓값이다.

배열 최적화

• 같은 물건을 여러 번 쓸 수 있으므로, 앞에서부터 순회 가능

  for i in range(n):
      for w in range(weight[i], capacity+1):
          dp[w] = max(dp[w], dp[w-weight[i]] + value[i])

배열최적화를 한다고 시간복잡도가 줄어드는 것은 아니다.

비교 정리 표

구분	0-1 Knapsack	Unbounded Knapsack
배낭 무게 제한	있음	있음
물건 사용 횟수	각 물건당 최대 1번	각 물건 무한히 가능
점화식	dp[i-1][...] 참조	dp[i][...] 참조
배열 최적화 순회	뒤에서 앞으로	앞에서부터
한줄 정리	물건 1번만 → 뒤에서부터 순회	물건 무한히 → 앞에서부터 순회

직접 문제를 풀어보자

• 12865 평범한 배낭

• 풀이 링크 : 🔗 개인 노션 링크
  

• 2293 동전 1

• 풀이 링크 : 🔗 개인 노션 링크
  

• 2294 동전 2

• 풀이 링크 : 🔗 개인 노션 링크
  

• 7579 앱

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 단순하게 디피 로직에 끼워맞히는게 아니라, 어떤 걸 찾으려고 DP를 적용하는 중인지 생각하면서 코드를 짜자 !!
  

다시 시작해보자

꾸준한 건 실패하지 않는게 아니라 실패해도 또 하는 것이다