🖊️ 문제

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

---

🖊️ 풀이

아.. 보자마자 배낭문제구나! 깨닫긴 했다.
근데 이제 배낭문제..
그거 어떻게 하는 거였더라......

이렇게 되어버렸다 ㅠㅠ
처음에 그래서 각 배낭을 선택하거나, 말거나로 했는데 당연히 틀렸다.

그니까 만약 예시와 같은 입력이 주어졌을 때,

40키로 담았을 때와 60키로 담았을 때의 최댓값을 각각 저장해줘야 한다는게 포인트.

그래서 다시 배낭문제를 천천히 이해하고 다시 풀었다.

---

모든 무게에 대해서, 이 배낭을 담았을 때의 중요도의 최댓값을 저장해준다.

배낭문제에 대한 풀이방법은 이 글에 작성했다.

배낭아ㅏ 이러지마아아..

#include <iostream>
using namespace std;

// 중요도, 시간
int arr[1001][2];
int dp[1001][10001] = { 0, };
int N, K;

void Select()
{
	for (int i = 1; i <= K; i++) {
		for (int j = 1; j <= N; j++) {
			if (arr[i][1] > j) dp[i][j] = dp[i-1][j];
			else dp[i][j] = max(dp[i - 1][j], arr[i][0] + dp[i - 1][j - arr[i][1]]);
		}
	}
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> N >> K;
	
	for (int i = 1; i <= K; i++) {
		cin >> arr[i][0] >> arr[i][1];
	}

	Select();

	cout << dp[K][N];
}