[SWEA] D.3 0/1 Knapsack

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJAVpqrzQDFAWr 

SW Expert Academy

 

 

1. 해결방법

DP로 해결하였는데 DP에 대해서 아직 숙달이 안되었다보니 다른 분들의 풀이를 참고했다. 
참고로 D3에 햄버거 문제와 마찬가지로 같은 로직의 DP 알고리즘을 사용하면 햄버거 문제와 똑같이 해결할 수 있다.

다만 햄버거 문제처럼 재귀를 이용해서 모든 경우를 재귀로 도는 방식은 시간 초과가 나온다.

https://ljw538.tistory.com/33
위의 블로그에서 어떻게 DP가 작동되는지 확인해보고 이해가 안간다면 i, j에 차근차근 대입해보면서 글을 읽어나가면 이해가 될 것이다.
본인은 그렇게 함;

 

 

2. 정답코드

T = int(input())
# T = 1
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N, K = map(int, input().split())
    back = [list(map(int, input().split())) for _ in range(N)]

    dp = [[0] * (K + 1) for _ in range(N + 1)]

    for i in range(1, N + 1):
        for j in range(1, K + 1):
            if j - back[i - 1][0] >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - back[i - 1][0]] + back[i - 1][1])
            else:
                dp[i][j] = dp[i - 1][j]

    print(f"#{test_case} {dp[N][K]}")

 

3. 재귀를 이용한 틀린 시간초과 코드

def dfs(idx, v, c):
    global answer

    if v > K:
        return

    if v <= K:
        answer = max(answer, c)

    if idx == N:
        return

    dfs(idx + 1, v, c)
    dfs(idx + 1, v + back[idx][0], c + back[idx][1])


T = int(input())
# T = 1
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N, K = map(int, input().split())
    back = [list(map(int, input().split())) for _ in range(N)]

    back.sort()

    answer = 0
    dfs(0, 0, 0)

    print(f"#{test_case} {answer}")