SWEA 5125번 햄버거 다이어트(python, knapsack,dfs)

냅색(Knapsack) 문제의 변형이다.
냅색 문제는 주어진 무게(=칼로리) 제한 아래에서 최대 가치(=맛점수)를 얻을 수 있는 아이템(=햄버거 재료)의 조합을 찾는 문제이다. 냅색 문제는 동적 프로그래밍(Dynamic Programming)으로 해결할 수 있다.
dfs로도 해당 재료를 선택한 경우와 선택하지 않은 경우로 나누어서 풀 수 있다.

✍🏻 접근 방법

1. dp[i][j]를 재료 i까지 고려했을 때, 칼로리 j를 넘지 않는 조건에서의 최대 점수로 정의
2. 각 재료를 순회하며, 해당 재료를 선택할 경우와 선택하지 않을 경우를 고려하여 dp 테이블을 업데이트

• 선택하지 않을 경우: dp[i][j] = dp[i-1][j]
  (이전 재료까지 고려했을 때의 최대 점수를 그대로 사용)
• 선택할 경우: dp[i][j] = max(dp[i-1][j], dp[i-1][j-Ki] + Ti) (이전 재료까지 고려했을 때의 최대 점수와 현재 재료를 추가했을 때의 최대 점수 중 더 큰 값)

🎒표

📖 답안1 (knapsack)

T = int(input())

for case in range(1, T + 1):
    N, L = map(int, input().split())  # 재료의 수와 제한 칼로리를 입력받음
    ingredients = [list(map(int, input().split())) for _ in range(N)]  # 각 재료의 점수와 칼로리를 입력받음

    dp = [[0] * (L + 1) for _ in range(N + 1)]  # 동적 프로그래밍을 위한 테이블 초기화

    for i in range(1, N + 1):
        Ti, Ki = ingredients[i-1]
        for j in range(1, L + 1):
            if Ki <= j:  # 현재 재료를 추가할 수 있는 경우
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-Ki] + Ti)
            else:  # 현재 재료를 추가할 수 없는 경우
                dp[i][j] = dp[i-1][j]

    print(f'#{case} {dp[N][L]}')  # 결과 출력

📖 답안2 (dfs)

def dfs(index, score, calorie):
    global max_score, N, L, ingredients
    # 제한 칼로리를 초과한 경우 더 이상 탐색하지 않음
    if calorie > L:
        return
    # 현재까지 조합의 점수가 최대 점수보다 큰 경우 업데이트
    if score > max_score:
        max_score = score
    # 모든 재료를 확인한 경우 탐색 종료
    if index == N:
        return
    # 현재 재료를 선택하는 경우
    dfs(index + 1, score + ingredients[index][0], calorie + ingredients[index][1])
    # 현재 재료를 선택하지 않는 경우
    dfs(index + 1, score, calorie)

# 입력
T = int(input())
for t in range(1, T+1):
    N, L = map(int, input().split())
    ingredients = [tuple(map(int, input().split())) for _ in range(N)]
    max_score = 0
    dfs(0, 0, 0)
    print(f"#{t} {max_score}")