다이나믹 프로그래밍

다이나믹 프로그래밍 = DP = Dynamic Programming

- 알고리즘의 과정에서 하나의 문제에 대해선 한 번만 풀도록 계획하는 알고리즘.

- 재귀함수같은 비효율적인 알고리즘을 개선하기 위한 방법.

- 이미 계산한 값을 저장했다가 재활용 한다고 생각하면 편하다.

- Top-down 방법과 Bottom-up 방법이 존재.

 

- Top-down 방법: 큰 문제에서 시작하여 작은 문제로 분할하며 푸는 것.

- 피보나치를 예로 들면 fb[5] = fb[4] + fb[3]이고 이에 따라서 fb[5]를 구하는 문제는 fb[4]와 fb[3]을 구하는 문제로 분할 가능.

- 재귀랑 비슷해 보이지만 계산한 값을 저장하여 이미 계산한 값이 있으면 꺼내쓰는 방법으로 효율성을 증대시킴.

Top-down 방법으로 구현한 피보나치 수열

 

- Bottom-up 방법: 작은 문제에서 시작하여 큰 문제로 확장시켜 나아가는 것.

- fb[2]를 구했다면 fb[3]을 구할 수 있고 fb[3]을 구했다면 fb[2]와 fb[3]을 통하여 fb[4]를 구할 수 있음.

Bottom-up 방법으로 구현한 피보나치 수열

 

- 2차원 배열로 동작하는 DP도 존재함.

- Backsack 문제는 물건을 가치로 내림차순 하여 하나씩 넣었을때 가치의 최댓값을 구하도록 하는 DP 활용 문제.

무게6 가치13

무게5 가치12

무게4 가치8

무게3 가치6

 

w(무게) i(물건 수)	w = 0	1	2	3	4	5	6	7 (최대 무게)
i = 0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	0	12	13
3	0
4	0

각 칸에 대하여 해당 칸의 윗칸과 현재 물건을 추가로 넣었을때(윗칸에서 추가하는 물건의 무게를 뺀 값) 가치를 비교

DP[1][6] = DP[0][6]과 DP[0][6 - 6(첫번째 물건의 무게)] + 13(첫번째 물건의 가치)을 비교하여 더 큰 13을 채택

DP[2][5] = DP[1][5]와 DP[1][5-5] + 12를 비교하여 더 큰 12을 채택

DP[2][6] = DP[1][6]과 DP[1][6-5] + 12를 비교하여 더 큰 13을 채택

 

w(무게) i(물건 수)	w = 0	1	2	3	4	5	6	7 (최대 무게)
i = 0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	0	12	13	13
3	0	0	0	0	8	12	13	13
4	0	0	0	6	8	12	13	14

 

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

int backsack[101][100001] = { 0, }; // [물건 갯수][무게]

int Backsack(vector<pair<int, int>> object_vector, int object_num, int weight_num)
{
	for (int object = 1; object <= object_num; object++)
	{
		int current_weight = object_vector.at(object - 1).first;
		int current_price = object_vector.at(object - 1).second;
		for (int weight = 1; weight <= weight_num; weight++)
		{
			if (current_weight <= weight)
			{
				backsack[object][weight] = max(backsack[object - 1][weight], backsack[object - 1][weight - current_weight] + current_price);
			}
			else
			{
				backsack[object][weight] = backsack[object - 1][weight];
			}
		}
	}
	return 0;
}

bool cmp(pair<int, int> num1, pair<int, int> num2)
{
	if (num1.second < num2.second) return false;
	else if (num1.second == num2.second)
	{
		if (num1.first < num2.first) return true;
		else return false;
	}
	else return true;
}

int main()
{
	int object_num;
	int weight_num;
	cin >> object_num >> weight_num;

	vector<pair<int, int>> object_vector;
	int cmd = object_num;
	while (cmd--)
	{
		int weight;
		int price;
		cin >> weight >> price;
		object_vector.push_back(pair<int, int>(weight, price));
	}
	sort(object_vector.begin(), object_vector.end(), cmp);

	Backsack(object_vector, object_num, weight_num);
	cout << backsack[object_num][weight_num] << endl;
}

백준 12865번 문제(https://www.acmicpc.net/problem/12865)