[백준] 12865번 : 평범한 배낭

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

12865번: 평범한 배낭

---

//C++

#include <bits/stdc++.h>
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi 3.1415926535

using namespace std;
typedef long long ll;
int weight[105];
int value[105];

int arr[105][100005];

int main()
{
	F_I;

	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		int w, v;
		cin >> w >> v;
		weight[i] = w;
		value[i] = v;
	}
	for (int i = 1; i <= n ; i++)
	{
		for (int j = 1; j <= k ; j++)
		{
			if (weight[i] > j)  //참고 1
				arr[i][j] = arr[i - 1][j];
			else  //참고 2
				arr[i][j] = max(value[i] + arr[i - 1][j - weight[i]], arr[i - 1][j]);
		}
	}

	cout << arr[n][k] << '\n';
}

(냅색 알고리즘, dp 이용)

 

-> 참고 1) 만약 임의의 물건이 j보다 크면 그 물건을 넣을 수 없으므로, 그 땐 바로 직전의 결과를 그대로 가져온다.

-> 참고 2)  i번째 물건을 넣어서 나올 수 있는 최대값, i번째 물건을 넣지 않고 나올 수 있는 최대값

              >> 이 두 개를 비교하여 max값을 넣어준다.