[알고리즘] C++ 백준 12865 배낭

 

백준 12865

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

12865번: 평범한 배낭

 

풀이 전 나의 생각

DP를 풀 때 생각해야 하는 두 가지

1. for문을 이용한 DP는 이전 값에 접근해야 되기 때문에 초기값을 0으로 설정해줘야 한다.

2. 어느 분기에 도착했을 때 이전에 구해 놓은 최대 값을 탐색해야 한다.

 

배낭의 들어갈 수 있는 물건들과 최대로 넣을 수 있는 무게가 주어진다.

이 때 최대 무게를 지키면서 가치를 최대로 높일 수 있도록 물건을 넣어야 한다.

 

현재 주어진 아이템의 종류는 4개 최대 무게는 7이다.

그러면 여기서 무게를 1부터 최대무게 까지 탐색하면서 어떤 무게의 상태에서 최고로 가치있는 배낭이 될 경우의 수를 구해야 한다. 이유는 DP를 풀 때 생각해야 하는 두 가지에서 2번이다. 

 

우선 문제에서 주어진 예제를 기준으로 아이템의 무게가 3을 넘는 것이 없으니 한계 무게가 1, 2일 때는 모두 0이 들어간다. 그럼 이제 한계 무게가 3일 때 무게가 3이면서 가치가 6인 세번 째 아이템을 넣을 수 있다.

(bag[3][3] = 6 -> 첫번 째 부터 3번 째 아이템까지 탐색중이면서 한계 무게가 3일 때 들어간 가치 값이 6)

 

세번 째 아이템 이후의 아이템은 모두 무게가 맞지 않기 때문에 한계가 3일 때 넣을 수 있는 최고 가치 값인 6을 

다음 아이템 순서에 넣어준다. (bag[3][3] ~ bag[4][3] = 6) 

 

다음으로 한계 무게가 4일 때 무게가 4면서 가치가 8인 두번 째 아이템을 넣을 수 있다.

(bag[2][4] = 8 -> 첫번 째 부터 2번 째 아이템을 탐색중이면서 한계 무게가 4일 때 들어간 가치 값이 6)

 

두번 째 아이템 이후의 아이템은 모두 무게가 맞지 않기 때문에 한계가 4일 때 넣을 수 있는 최고 가치 값인 8을 

다음 아이템 순서에 넣어준다. (bag[2][4] ~ bag[4][4] = 8) 

 

다음으로 한계 무게가 5일 때 무게가 5면서 가치가 12인 네번 째 아이템을 넣을 수 있다.

(bag[4][5] = 12-> 첫번 째 부터 5번 째 아이템을 탐색중이면서 한계 무게가 5일 때 들어간 가치 값이 12)

 

네번 째 아이템 이후의 아이템은 모두 무게가 맞지 않기 때문에 한계가 5일 때 넣을 수 있는 최고 가치 값인 12을 

다음 아이템 순서에 넣어준다. (bag[4][5] ~ bag[4][5] = 12) 

 

다음으로 한계 무게가 6일 때 무게가 6이면서 가치가 13인 첫번 째 아이템을 넣을 수 있다.

(bag[1][6] = 13-> 첫번 째 부터 첫번 째 아이템을 탐색중이면서 한계 무게가 6일 때 들어간 가치 값이 13)

 

첫번 째 아이템 이후의 아이템은 모두 무게가 맞지 않기 때문에 한계가 6일 때 넣을 수 있는 최고 가치 값인 13을 

다음 아이템 순서에 넣어준다. (bag[1][6] ~ bag[4][6] = 13) 

 

마지막 한계 무게인 7에 도달 했을 때 선택해야 할 분기 두 가지로 나뉜다.

 

1. 한계 무게가 7이면서 바로 이전의 아이템을 선택 했을 때 나올 수 있는 최대 가치 값을 선택한다.

2. 현재 한계 무게에서 선택된 아이템의 무게를 뺀 한계 무게에서 바로 이전의 아이템을 선택했을 때 나올 수있는

최대 가치 값과 현재 선택된 아이템의 가치 값을 더해준다.

 

2번이 굉장히 헷갈릴 수 있다. 한계 무게가 7일 때 세번 째 아이템을 선택했다고 가정하자.

무게 3, 가치 6인 세번 째 아이템은 바로 이전의 아이템 까지 선택된 최고의 가치 값을 가져와야 하기 때문에 현재 한계 무게인 7에서 선택된 아이템의 무게 3을 뺀다.

그럼 한계 무게는 4가 되는데 이 때 바로 이전 아이템까지 탐색을 진행한 경우에서 한계 무게가 4인 최고의 가치값을 가져온다면 현재 선택된 아이템의 가치 값과 더하여 최고의 가치합을 구할 수 있게 된다.

 

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>

using namespace std;

int bag[101][100001];
int n, k = 0;
vector<pair<int, int>> item;

void dp() 
{
	for (int limit = 1; limit <= k; limit++)
	{
		for (int i_num = 1; i_num <= n; i_num++)
		{
			if (limit < item[i_num].first)
			{
				bag[i_num][limit] = bag[i_num - 1][limit];
			}
			else
			{
				bag[i_num][limit] = max(bag[i_num - 1][limit - item[i_num].first] + item[i_num].second, bag[i_num - 1][limit]);
			}
		}
	}
}

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

	cin >> n >> k;
	item.push_back({0, 0});
	for (int i = 0; i < n; i++)
	{
		int w, v;
		cin >> w >> v;
		item.push_back({w, v});
	}
	
	dp();

	cout << bag[n][k];
}