[SWEA] Q5215 햄버거 다이어트

[SWEA] Q5215 햄버거 다이어트

Question

Language: Python

Difficulty: D3

전형적인 0/1 Knapsack 유형의 문제이다. 각각의 햄버거에 대해서 해당 햄버거를 취하는 경우, 그렇지 않은 경우를 비교하면서 최대 칼로리를 섭취 했을때의 최대 만족도를 구한다.

if j>=calorie:
    dp[i][j]=max(dp[i-1][j], dp[i-1][j-calorie]+score)
else:
    dp[i][j]=dp[i-1][j]

Solution

def solution():
    dp=[[0] * (max_calorie +1) for _ in range(n)]

    for i in range(n):
        score,calorie=scores[i],calories[i]
        for j in range(max_calorie+1):
            if j>=calorie:
                dp[i][j]=max(dp[i-1][j], dp[i-1][j-calorie]+score)
            else:
                dp[i][j]=dp[i-1][j]

    return dp[n-1][max_calorie]

if __name__ == "__main__":
    with open("input.txt", "r") as file:
        test_cases=int(file.readline())
        for case in range(test_cases):
            n, max_calorie=map(int,file.readline().split())
            scores=[]
            calories=[]
            for _ in range(n):
                score,calorie=map(int,file.readline().split())
                scores.append(score)
                calories.append(calorie)
            print(f"#{case+1} {solution()}")