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

백준 12865번 0-1 knapsack 문제. 단계 동적 계획법1에 위치해 있다.

한번에 맞추긴 했는데 개같이 어려웠다 진짜.. 눈물 줄줄흘렸음 vs에서 얼마나 수정을 거듭한거지..

이번에 푼 문제는 0-1 knapsack 문제인 12865번 평범한 배낭 문제를 풀었다.

솔직히 이런말하긴 뭐하지만 개갓이 어려웠다. 진짜진짜진짜 개갓이

아니 문제 아니 알고리즘이 이렇게 어려워도 됨? 이거 공부부터 해석하는데만 기절하는줄 알았음...

 

이거도 다이나믹 프로그래밍의 종류인, 0-1 knapsack(배낭)문제이다.

보통의 배낭 문제라고 한다면 그리디 알고리즘으로 해결할 수 있는데, 0-1 knapsack문제는 다르다. 그리디 알고리즘으로 푼다면 최적값이 아니기 때문에 틀려버리는데, 동적 계획법이나 백트래킹기법으로 접근해야만 문제를 해결할 수 있다.

 

아니 나도 너무 어려워서 관련 알고리즘 짜는 법을 검색해보고 공부했는도 아직 어려웠다ㅠ

#include <iostream>
using namespace std;

int W[101]; // 물품의 무게
int V[101]; // 가치
int dp[101][100001]{};  // 가치의 최대

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	int weight; // 물품의 개수
	int kilogram; // 버틸 수 있는 무게
	cin >> weight >> kilogram;
	
	for (int i = 1; i < weight+1; ++i)
	{
		cin >> W[i] >> V[i];
	}

	for (int i = 1; i <= weight; ++i)
	{
		for (int j = 1; j <= kilogram; ++j)
		{
			if (j - W[i] >= 0)
			{
				dp[i][j] = max(dp[i - 1][j], (dp[i - 1][j - W[i]] + V[i]));
			}
			else dp[i][j] = dp[i - 1][j]; // j가 W[i]보다 클 때 
		}
	}

	cout << dp[weight][kilogram];

}

무게를 비교해가며 최대값을 늘려가는데, 이때 무게가 w[i]보다 낮으면 전값으로 돌리고, 어쩌고 저쩌고...

아니라면 이전값과 새로 추가하는 값의 가치의 합들을 계산해보고 둘중 최대값으로 그 값을 설정한다.

이런식으로 무게를 하나하나 늘려가면서 해당 무게의 가져갈 수 있는 물건 가치의 최대값을 찾아내는 방법이다.

 

저번에 올렸던 동적계획법 피보나치 수와 비슷하게, 전값을 저장해두고 다음 값으로 넘어갈 때 전값과 비교하는? 그렇게 접근해야 한다.

그리디였으면 대충 제일 큰값부터 추가해서 했을텐데, 그러면 당연히 틀릴수밖에 없는게, 각 무게들마다 가치가 다 다르기 때문이다.

 

 

문제를 풀긴 했지만, 뭔가 너무 어려워서 제대로 이해하지 못하고 대충 값을 쑤셔넣어 푼 것 같다.

이게 골드5? 아직 내 뇌는 실버따리에서 머물러있는 걸지도 모른다...

이건 111번째 문제를 해결했다고 봐야하나..?  같은 0-1 knapsack의 다른 문제를 풀어보면서 다시 생각해봐야겠다.

그러고 나서는 다른 알고리즘으로 넘어가야지