[C++] 백준 12865 : 평범한 배낭

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

12865번: 평범한 배낭

백준 12865번 평범한 배낭 문제를 풀었습니다.

0-1 냅색 문제입니다. 

arr[i][j]는 배낭 용량이 j일 때, 첫 번째 물건부터 i번째 물건까지 넣어본 최댓값을 가지고 있습니다.

i번째 물건의 무게가 j보다 크다면 가방에 물건을 넣을 수 없으므로 arr[i][j]는 arr[i-1][j]이 됩니다.

i번째 물건의 무게가 j보다 같거나 작다면 가방에 넣을 수 있으므로 i번째 물건을 가방에 넣은 경우와 넣지 않았을 경우를 비교해서 더 큰 가치를 arr[i][j]에 저장하면 됩니다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int N;
int thing[101][2];
int K;
int arr[101][100001];

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

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

	dp(N, K);

	cout << arr[N][K];

	return 0;
}