[백준 12865] 평범한 배낭 (C++)

문제 링크: https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

1. 주의할 점

- Greedy를 이용한 방법으로 하지 말것(TC부터 답이 틀릴것이다)

- Knapsack 알고리즘에 대해 알고 있어야 한다

 

2. 구현

- Dp[][]배열을 전부 -1로 초기화한다

- Arr[][]배열을 통해 각 물건의 무게, 가치를 저장한다

- Dp[][]배열을 통해 해당 Idx전까지 Remain만큼의 양을 남기고 가치의 최대값을 구한적이 있는 경우, 재사용한다(시간 절약 -> TLE발생 x)

- Idx번째에 있는 물건을 추가할 만큼 공간이 남아있다면 물건을 추가하고, 추가하지 않고 그냥 넘어간것과 비교하여 DP를 갱신한다

- Temp와 Result를 비교하여, Result에는 가방에 채울 수 있는 최대의 가치가 들어가도록 한다(가방의 무게와 물건 무게들의 합이 딱 맞아 떨어지지 않는 경우를 대비하여 매번 초기화 한다)

 

#include <iostream>
#include <algorithm>
using namespace std;
long long dp[100][100001], result = 0;
int arr[100][2];		//무게, 가치
int num, weight;

long long knapsack(int idx, int remain) {
	if (idx == num) return 0;
	long long temp = dp[idx][remain];
	if (temp != -1) return temp;
	if (arr[idx][0] <= remain) 		//추가 가능
		temp = knapsack(idx + 1, remain - arr[idx][0]) + arr[idx][1];
	temp = max(temp, knapsack(idx + 1, remain));
	result = max(result, temp);
	return dp[idx][remain] = temp;
}

int main() {
	cin >> num >> weight;
	for (int i = 0; i < num; i++) {
		cin >> arr[i][0] >> arr[i][1];
		for (int j = 0; j <= weight; j++)
			dp[i][j] = -1;
	}
	knapsack(0, weight);
	cout << result;
	system("pause");
	return 0;
}