[SWEA 5258][Python] [파이썬 S/W 문제해결 최적화] 3일차 - 해피박스

코드1 - DFS 

## SWEA 5258 dfs 풀이
T = int(input())
def dfs(w,k,local_value):
    global result
    if w >= 0 :
        if k > N :
            if result < local_value :
                result = local_value
        else :
            dfs(w-w_arry[k],k+1,local_value+v_arry[k])
            dfs(w, k + 1, local_value)


for test_case in range(1,T+1):
    W,N = map(int, input().split())
    w_arry = [0 for _ in range(N+1)]
    v_arry = [0 for _ in range(N+1)]
    for i in range(1,N+1):
        w_arry[i], v_arry[i] = map(int, input().split())
    result = 0

    dfs(W,0,0)
    print(f"#{test_case} {result}")

풀이1

weight list 와 value list를 가지고 k번째 상품을 담을 경우/ 담지 않을 경우를 분리하여 재귀 호출 했다. 

이번 단원은 DP 적용 단원이니까 DP를 활용해서 또 풀어보기로 했다. 

 

 

 

코드2

## SWEA 5258 dp 풀이
def happybox():
    for i in range(N+1):
        r_arry[i][0] = 0
    for w in range(W+1):
        r_arry[0][w] = 0

    for i in range(1, N+1):
        for w in range(1, W+1):
            if w_arry[i] > w :
                r_arry[i][w] = r_arry[i-1][w]
            else :
                r_arry[i][w] = max( r_arry[i-1][w-w_arry[i]] + v_arry[i], r_arry[i-1][w] )

T = int(input())
for test_case in range(1,T+1):
    W,N = map(int, input().split())
    w_arry = [0 for _ in range(N+1)]
    v_arry = [0 for x in range(N+1)]
    r_arry = [ [0]*(W+1) for _ in range(N+1) ]
    for i in range(1,N+1):
        w_arry[i], v_arry[i] = map(int, input().split())
    happybox()
    print(f"#{test_case} {r_arry[N][W]}")

풀이2

r_arry 라는 물건과 weight의 포함 여부에 따른 value 변화를 저정하는 2차원 list를 선언하였다.

추가로 담을 물건 때문에 weight가 넘어가면 물건을 담지 않고, 물건을 담을 수 있는 경우에는 

해당 물건을 추가했을때의 value와 기존에 업데이트되어 있던 value를 비교하여 큰 값을 업데이트 했다.