백준 12865번 평범한 배낭

 

 

 

문제 보러가기 :  https://www.acmicpc.net/problem/12865

 

 

 

12865번: 평범한 배낭

 

 

 

이번 문제는 다이나믹 프로그래밍(DP) 문제였습니다. 

 

 

 

 

《문제 풀이》

 

1. 물건의 무게와 가치를 쌍으로 묶어서 벡터에 삽입

2. 물건들의 가치합을 담을 배열 dp 초기화

     (1) dp 배열의 행은 물건을 나타내고 (첫번째 물건, 두번째 물건, ...) 열은 물건의 무게를 나타냄 (0 ~ K)

     (2) 첫번째 물건의 무게부터 K까지 첫번째 물건의 가치를 넣어줌

3. 이중 포문을 돌면서 물건들의 가치합의 최댓값 구하기

     (1) 현재 물건의 무게와 현재 물건의 가치를 각각 변수에 저장

     (2) 0 ~ K 까지 돌면서 넣으려는 물건의 무게가 해당 무게보다 크면 (현재 물건을 배낭에 넣을 수 없으므로) 

          --> dp[i][j] = dp[i - 1][j]

     (3) 넣으려는 물건의 무게가 해당 무게보다 작거나 같으면 (현재 물건을 배낭에 넣을 수 있음)

          --> dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value) 

4. dp[ N - 1 ][ K ] 출력

 

 

 

 

《C++ 코드》

 

#include <bits/stdc++.h>

using namespace std;

int dp[100][100001];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int N, K;
	cin>>N>>K;
	
	vector<pair<int, int>> v;
	for(int i=0; i<N; i++) {
		int weight, value;
		cin>>weight>>value;
		
		// 물건의 무게와 가치 페어로 삽입  
		v.push_back({ weight, value });
	}
	
	// dp 초기화  
	for(int i=v[0].first; i<=K; i++)
		dp[0][i] = v[0].second;
		
	for(int i=1; i<N; i++) {
		int weight = v[i].first;
		int value = v[i].second;
		
		for(int j=0; j<=K; j++) {
			
			// 해당 무게가 넣으려는 물건의 무게보다 작으면  
			if(j < weight)
				dp[i][j] = dp[i - 1][j];
			else 
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value);
		}
	}

	cout<<dp[N-1][K]; // 물건들의 가치합의 최댓값  
	return 0;
}

 

 

개발 환경: Dev-C++

 

 

 

baekjoon - 정답 화면