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

 

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

 

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

12865번: 평범한 배낭

---

 

해결전략

 

Dynamic Programming 다이나막 프로그래밍

배낭 문제

---

 

 

풀이

 

int n, k;

• n  물품의 수, 
• k  배낭의 최대 수용 무게

 

vector<int> w, v;

• w[ i ]  각 물건의 무게
• v[ i ]  각 물건의 가치

 

 

if (j >= w[i])
	dp[i][j] = max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]]);
else
	dp[i][j] = dp[i - 1][j];

 

 

• 현재 탐색 중인 물건 i의 무게(  w[ i ]  )가 j보다 작거나 같을 경우(즉, 현재 배낭 무게 j에 다른 물건들과 함께 물건 i를 담을 수 있을 경우),
  • 이전까지의 물건들에서 최대 가치 dp[ i - 1 ][ j ]와 현재 물건 i의 가치(  v[ i ]  )와 다른 물건들로 채워진 배낭의 가치(  dp[ i - 1 ][ j - w[ i ]]  ) 를 합산한 값 중에서 최대값을 선택하여 dp 배열에 저장.

 

• 현재 물건 i의 무게가 j보다 클 경우(즉, 현재 배낭 무게 j에 물건 i를 담을 수 없을 경우),
  • 이전까지의 물건들에서 구한 최대 가치 dp[ i - 1 ][ j ] 를 그대로 사용한다.

 

마지막 값인 dp[ n ][ k ] 는 n개의 물건과 최대 무게 k인 배낭을 고려했을 때 얻을 수 있는 배낭에 담긴 물건들의 최대 가치다.

 

 

 

입력값

4 7
6 13   - i 첫번째 물건
4 8     - i 두번째 물건
3 6     - i 세번째 물건
5 12   - i 네번째 물건

 

 

dp[ i ][ j ] 

i \ j	[][1]	[][2]	[][3]	[][4]	[][5]	[][6]	[][7]	[][8]	[][9]	[][10]	[][11]	[][12]	[][13]	[][14]	[][15]	[][16]	[][17]	[][18]	[][19]
[1][]	0	0	0	0	0	13	13	13	13	13	13	13	13	13	13	13	13	13	13
[2][]	0	0	0	8	8	13	13	13	13	21	21	21	21	21	21	21	21	21	21
[3][]	0	0	6	8	8	13	14	14	19	21	21	21	27	27	27	27	27	27	27
[4][]	0	0	6	8	12	13	14	18	20	21	25	26	27	31	33	33	33	39	39
	dp[1][]는 첫번째 물건만 가지고 만들 수 있는 무게와 최대가치 dp[2][]는 첫번째 + 두번째 물건만 가지고 만들 수 있는 무게와 최대가치 dp[3][]는 첫번째 + 두번째 + 세번째 물건만 가지고 만들 수 있는 무게와 최대가치 dp[4][]는 첫번째 + 두번째 + 세번째 + 네번째 물건만 가지고 만들 수 있는 무게와 최대가치

 

---

 

 

코드

 

#include <iostream>
#include <vector>
using namespace std;

int n, k;//n은 물품의 수, k는 배낭의 최대 수용 무게
vector<int> w, v;//w는 각 물건의 무게, v는 물건의 가치
vector<vector<int>> dp;

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

	cin >> n >> k;
	w.resize(n + 1);
	v.resize(n + 1);

	for(int i = 1; i <= n; i++){
		//물건의 무게(w)와 가치(v)를 각각 다른 배열에 담는다.
		cin >> w[i] >> v[i];
	}

	//dp[i][j]의 값 = i개의 물건과 현재 배낭의 무게 j를 고려할 때 배낭에 담긴 물건들의 최대 가치
	//dp[i][j]배열에 i이하 개수의 물건, j이하의 무게로 가질 수 있는 물건의 최대 가치를 담는다.
	dp.resize(n + 1, vector<int>(k + 1));

	for(int i = 1; i <= n; i++)//i는 물건의 개수
	{
		for (int j = 1; j <= k; j++)//j는 배낭의 무게
		{
			if (j >= w[i])//현재 탐색 중인 물건 i의 무게(w[i])가 j보다 작거나 같을 경우(즉, 현재 배낭 무게 j에 다른 물건들과 함께 물건 i를 담을 수 있을 경우)
				dp[i][j] = max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]]);
			else//현재 물건 i의 무게가 j보다 클 경우(즉, 현재 배낭 무게 j에 물건 i를 담을 수 없을 경우)
				dp[i][j] = dp[i - 1][j];
		}
	}


	cout << dp[n][k];   

	return 0;
}

 

 

 

 

---