https://www.acmicpc.net/problem/12865
평범한 배낭 문제는 0 1 배낭 문제의 가장 전형적인 문제이다. 배낭 문제(Knapsack Problem)는 조합 최적화의 유명한 문제로 간단히 말하면, 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.
완전 탐색
n개의 물건이 있을 때 챙길지 말지를 고려한 모든 조합은 2^N개의 경우의 수가 나온다.
O(2^N)이 되버리면 시간안에 문제를 푸는 건 사실상 불가능하다.
DP
i는 N번째 물건을 가방에 넣을 것을 고려하는지를
j는 가방의 최대 용량을 의미한다.
dp[i][j] = dp[i - 1][j] (if weights[i] > j)
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weigthts[i]] + values[i]) (else)코드
N, K = map(int, input().strip().split())
values = [0] * (N + 1)
weights = [0] * (N + 1)
for i in range(1, N + 1):
_weight, _value = map(int, input().strip().split())
weights[i] = _weight
values[i] = _value
dp = [[0] * (K + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
for j in range(1, K + 1):
if weights[i] > j:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i])
print(dp[N][K])참고
여담
처음 구조를 이해하는 것과 이 문제를 DP로 풀어야 한다는 걸 알기 까지 정말 오래걸렸다.
DP는 주어진 요구사항을 수학적 귀납법으로 변환하는 법을 아는지를 묻는 문제라 그런지 늘 쉽지않다고 느낀다
