[백준][12865] 평범한 배낭

이 포스트는 백준 사이트의 평범한 배낭 문제 풀이입니다.

문제

해결 과정

이 문제는 다이나믹 프로그래밍(DP)로 해결할 수 있는 대표적인 문제입니다.

준서는 최대 K 까지 배낭에 담을 수 있으므로 K 이하인 물건은 모두 담을 수도 있습니다.

따라서 DP 테이블을 사용하여 N개의 물건을 최대 K 까지 담았을 때의 값을 구하였습니다.

코드 구현

#include <iostream>
#include <vector>

using namespace std;

int DP[101][100001] = { 0, };

int main() {
	int N, K;
	cin >> N >> K;
	vector<pair<int, int>> vec{ {0, 0}, };

	for (int obj = 1; obj <= N; ++obj) {
		int w, v;
		cin >> w >> v;

		if(w <= K) {
            vec.emplace_back(make_pair(w, v));
        }
	}

	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= K; ++j) {
			int weight = vec[i].first;
			int value = vec[i].second;

			if (weight <= j) {
				if ((value + DP[i - 1][j - weight]) > DP[i - 1][j]) {
					DP[i][j] = value + DP[i - 1][j - weight];
                }
				else {
					DP[i][j] = DP[i - 1][j];
                }
			}
			else {
				DP[i][j] = DP[i - 1][j];
            }
		}
	}
	cout << DP[N][K];
	return 0;
}

실행 결과