[백준][DP] 12865. 평범한 배낭

12865. 평범한 배낭

 

 

• 풀이
  • 백트래킹으로 짜보기
  • 매번 2가지 선택지가 있기 때문에 2^n 으로 터짐 N(1 ≤ N ≤ 100)

n,k=map(int,input().split())
stucks=[list(map(int,input().split())) for _ in range(n)]

ans=0
def recur(cur, total_w, total_v):
    global ans
    if total_w>k:
        return
    if cur==n:
        ans=max(ans,total_v)

    for i in range(cur,n):
        recur(cur+1, total_w+stucks[i][0], total_v+stucks[i][1])
        recur(cur+1, total_w, total_v)
    
recur(0,0,0)
print(ans)

 

 

DP 풀이 (top-down)

• total_v 가 중요한 값 -> dp 값으로 빼기
• 나머지 파라미터들의 dp의 인덱스가 되는 것 dp[cur][total_w]
  • 기저조건 w>m일때를 큰 손해로 바꾸기
    • w>m 이면 기준치보다 크니까 이미 뭘해도 안되는 값을 주는 것
  • cur==n이면 return 0
    • 모든 물건에 대해 골라봤으니 끝내라
    • 남은 선택지에서 얻을 수 있는 가치가 없다는 의미→ return 0
  • dp[cur][w] ≠1 이미 방문했으면 바로 리턴
    • 리턴값에 영향을 주는 외부요인이 없기때문에 항상 일정한 값 제공
  • 고르거나, 안고르거나 중 더 큰 것

n,k=map(int,input().split())
stucks=[list(map(int,input().split())) for _ in range(n)]

dp=[[-1]*(k+1) for _ in range(n)]
def recur(cur, total_w):
    if total_w>k:
        return -43534852352
    if cur==n:
        return 0
    if dp[cur][total_w]!=-1:
        return dp[cur][total_w]

    dp[cur][total_w]=max(recur(cur+1, total_w+stucks[cur][0])+stucks[cur][1], recur(cur+1, total_w))

    return dp[cur][total_w]
    
print(recur(0,0))