백준 12865 : 평범한 배낭 c++ 정답 (배열 사용)

1. 입력 n 과 k를 받음

2. n개 만큼 무게와 가치의 pair를 받음

3. dp배열을 nxk크기로 만듦

4. 물건을 가져가기로 선택했을 때 얻는 가치를 배열에 넣어줌, 안가져가면 이전 배열의 값을 넣어줌

5. dp[i][j] = max(dp[i-1][j], i위치의 가치 + dp[i-1][j-i의 무게])

https://github.com/o920/baekjoon/blob/master/12865.cpp

o920/baekjoon

#include <iostream>
#include <algorithm>
using namespace std;
pair<int, int> N[100];
int dp[100][100001];
int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> N[i].first >> N[i].second;

	for (int i = 0; i <= k; i++) {
		if (N[0].first <= i)dp[0][i] = N[0].second;
		else dp[0][i] = 0;
	}
	for (int i = 1; i < n; i++) {
		for (int j = 0; j <= k; j++) {
			if (N[i].first <= j) dp[i][j] = max(dp[i - 1][j], N[i].second + dp[i - 1][j - N[i].first]);
			else dp[i][j] = dp[i - 1][j];
		}
	}

	cout << dp[n - 1][k] << endl;
}

---

(이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받을 수 있습니다.)