[백준] 12865번 : 평범한 배낭 (파이썬)

문제

나의 답안

n,k=map(int,input().split())
total=[[0,0]]

dp=[[0 for i in range(k+1)] for i in range(n+1)]#칼럼(무게), 열(개수) 2차원 배열

for i in range(n):
    w,v=map(int,input().split())
    total.append([w,v])

for i in range(1,n+1):
    for j in range(1,k+1):
        w=total[i][0]
        v=total[i][1]
        if w>j:#무게보다 크면 넣을 수 없음
            dp[i][j]=dp[i-1][j] #현재 이전의 물건들의 가중치만 저장
        else:#무게보다 작다면
        	#현재 물건을 담을 것인지 아닐 것인지 결정
            dp[i][j]=max(dp[i-1][j-w]+v,dp[i-1][j])
             
print(dp[n][k])

접근 방법

• 배낭 문제이다. dp로 풀어주어야 한다.
• 무게와 가치를 모두 고려해주어야 한다. 현재 가치가 가장 좋더라도 후에 더 좋은 가치를 갖는 물건이 나올 수 있으므로 담을지 말지를 고민해야 한다.
• 물건의 무게(w)가 수용 가능한 무게(k)보다 크면 담을 수 없고,
  아니라면 현재 물건을 담을지 말지를 정해주어야 한다.
• 현재 물건을 담는다면 수용 가능한 무게에서 현재 물건의 무게를 뺀 만큼의 가중치를 담을 수 있게 된다. 따라서 (k-현재 물건의 무게)+현재 물건의 가치(v)
  현재 물건을 담지 않는다면 이전까지의 가중치의 합을 저장한다.
  둘 중 큰 값을 dp에 저장한다.