백준 12865 평범한 배낭

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

서론

어디서 본것같은 문제였는데 풀어보니 처음본다.

공부해놓고 잊은건 실망스러우니 어디서 본것같은건 반드시 착각이다.

풀이

유명한 문제라고 해서 크게 고민 안하고 배낭문제를 검색했다.

참고한 사이트는

https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C

https://huiyu.tistory.com/entry/DP-01-Knapsack%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C

배낭문제를 모르고, 위의 참고한 사이트를 읽어보지 않으면 아래의 내용은 이해할 수 없다.

dp의 행은 아이템, 열은 무게다.

무게 3짜리를 기준으로

dp[0][0] ~ dp[0][2]는 아무것도 넣을 수 없다. dp[i][j] = 0 = dp[i-1][j]

dp[0][3] ~ dp[0][7]는 3을 넣을 수 있다. dp[i][j] = 3 = v[i]

무게 4짜리를 기준으로

dp[1][0] ~ dp[1][2]는 아무것도 넣을 수 없다. dp[i][j] = 0 = dp[i-1][j]

dp[1][3]은 3을 넣을 수 있다. dp[i][j] = dp[i-1][j]

dp[1][4]는 3을 넣을 수 있고 4를 넣을 수 있다. 둘 중 가치가 큰것은 4이므로 4를 넣는다. dp[i][j] = max(dp[i-1][j], v[i])

dp[1][7]은 3과 4를 같이 넣을 수 있다. dp[i][j] = dp[i-1][j-w]+v[i]

...

위 내용을 모두 포함하여 점화식으로 만들면

if (w>j) dp[i][j] = dp[i-1][j] // 현재 아이템을 넣을 수 없을때

else dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v[i]) // 현재 아이템을 넣을 수 있을 때

구현

//c++

#include <iostream>
#include <algorithm>

int dp[101][100001];
std::pair<int, int> item[101];
int n, k;

void input() {
	std::cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		std::cin >> item[i].first >> item[i].second;
	}
	std::sort(item, item + n + 1);
}

int cal() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (item[i].first > j) dp[i][j] = dp[i - 1][j];
			else dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - item[i].first] + item[i].second);
		}
	}
	return dp[n][k];
}

int main() {
	input();
	std::cout << cal();
}