20200804 // 삼성 SW Expert 아카데미 문제 // 3282

삼성 SW Expert 아카데미 3282번 "0/1 Knapsack" 문제입니다.

TC = int(input())   

def knapsack(W, wt, val, n):  # W: 배낭의 무게한도, wt: 각 보석의 무게, val: 각 보석의 가격, n: 보석의 수
    K = [[0 for x in range(W+1)] for x in range(n+1)]  # DP를 위한 2차원 리스트 초기화
    for i in range(n+1):
        for w in range(W+1):  # 각 칸을 돌면서
            if i==0 or w==0:  # 0번째 행/열은 0으로 세팅
                K[i][w] = 0
            elif wt[i-1] <= w:  # 점화식을 그대로 프로그램으로
                K[i][w] = max(val[i-1]+K[i-1][w-wt[i-1]], K[i-1][w])  # max 함수 사용하여 큰 것 선택
            else:
                K[i][w] = K[i-1][w]
    return K[n][W]
ans = []
for tc in range(1, TC + 1):
    k = "#"+str(tc)
    wt = []
    val = []
    N, K = map(int, input().split())
    for i in range(N):
        w, v = map(int, input().split())
        wt.append(w)
        val.append(v)
    k += " " + str(knapsack(K, wt, val, N))
    ans.append(k)
for e in ans:
    print(e)

 

DP로 유명한 Knapsack 문제이다. 공부를 하기 위해 다른 분의 블로그를 참고했다.

 

참고 블로그 : https://gsmesie692.tistory.com/113

Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)

 

DP 알고리즘 문제를 보면 막막했는데 이 분의 글을 참고하고 공부를 하니 좀 이해가 됐다. 다음 DP문제를 만나면 참고

 

해서 풀어봐야겠다.