https://www.acmicpc.net/problem/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값을 넣어준다.
'Problem Solving > 백준' 카테고리의 다른 글
[백준] 7569번 : 토마토 (0) | 2020.08.22 |
---|---|
[백준] 1012번 : 유기농 배추 (0) | 2020.08.18 |
[백준] 11052번 : 카드 구매하기 (0) | 2020.08.10 |
[백준] 16929번 : Two Dots (0) | 2020.08.04 |
[백준] 10972번 : 다음 순열 (0) | 2020.07.16 |