백준 12865번 평범한 배낭

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

knapsack 문제, 그중에서도 0-1 knapsack 문제이다.

 

동적 알고리즘을 활용하여 문제를 해결할 수 있다.

# 입력 받기
n, k = map(int, input().split())
things = [[0, 0]]	# 동적 프로그래밍을 위한 초기화
for i in range(n):
    w, v = map(int, input().split())
    things.append((w, v))

# 동적 프로그래밍을 위한 초기화
dp = [[0 for _ in range(k+1)] for _ in range(n+1)]

# 알고리즘 진행
for i in range(1, n+1):
    weight = things[i][0]
    value = things[i][1]
    for j in range(1, k+1):
        if j >= weight:  # j가 현재 물건의 무게 이상이면
            # 이전 물건 까지 / 지금 물건 포함 둘 중 가치가 큰 경우를 넣음
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value)
        else:
            dp[i][j] = dp[i - 1][j]

print(dp[n][k])

물건을 차례로 선택해가며 이전까지의 선택과 지금 선택한 물건을 대신 넣는 경우의 가치를 비교한다.

 

그렇게 무게와 물건에 따른 최선의 경우의 가치를 dp 배열에 저장해나간다. (동적 프로그래밍)

 

반복문이 끝나면 배열의 제일 끝에 최선의 경우의 가치가 저장된다.