Baekjoon12865-평범한 배낭

백준 사이트 12865 - 평범한 배낭 문제입니다.

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

DP문제입니다.
유명한 배낭 문제입니다.
백준에서는 Gold5의 난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 옛날에 파이썬으로 비슷한 문제를 푼 적이 있었는데, 그 때는 굉~~장히 어렵게 풀었기에 어려운 감이 있었는데, 여전히 어렵습니다..

• 재귀로 풀려다 트리까지 만들어줘야할 것 같아서 그냥 고민하다가 다른사람들의 코드를 참고하였습니다.
  • 굉장히 비효율적인 코드 같은데.. 고민하기가 더 힘듭니다.
• 코드의 내용은 각각 배낭마다 넣었을 때와 안 넣었을 때를 비교하는 간단한 로직이긴 합니다.

---

5. code

#include<iostream>
#include<algorithm>

using namespace std;

int n, k;

class bag
{
public:
	int w;
	int v;
};

bag arr[101];
int dp[101][100002];

void Input()
{
	cin >> n >> k;
	for (int i = 1; i <= n; ++i)
	{
		cin >> arr[i].w;
		cin >> arr[i].v;
	}

}

void Solve()
{
	int result = 0;
	for (int i = 1; i <= n; ++i)
	{
		int weight = arr[i].w;
		int val = arr[i].v;
		for (int j = 0; j <= k; ++j)
		{
			if (j < weight)
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i-1][j - weight] + val);
		}
	}
	cout << dp[n][k];
}

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

	Input();
	
	Solve();

	return 0;
}

---

6. 후기

나는 왤케 어려워.