BOJ 12865, 평범한 배낭
ProblemSolving ·이 문제는 냅색 알고리즘 문제입니다. DP라고 해도 무방합니다.
풀이
정해진 무게 안에서 가장 가치있게 가방에 담아내는 문제입니다.
‘dp[인덱스][남은무게]=최대 가치’ 로 식을 정해서 풀었습니다.
재귀호출을 할때마다 now+1을 해서 다음 인덱스의 값을 봐줍니다. 가방에 들어갈 수 있다면 물건을 담아봅니다.
그리고 원래 dp값과 비교해서 더 큰 값을 dp에 저장해줍니다.
이렇게 재귀로 완전탐색을 해서 최대 가치의 값을 리턴해줍니다.
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int n, k, w[101],v[101], dp[105][100005];
int go(int now,int cap)
{
if (now == n+1) return 0; // n번째 인덱스까지 비교하고 n+1까지 넘어왔을때 0을 return 해줍니다.
int& ret = dp[now][cap];
if (ret != -1) return ret;
if (w[now] <= cap) ret = go(now + 1, cap - w[now]) + v[now]; //남은 무게에서 물건의 무게를 빼주고 물건의 가치를 더해줍니다.
ret = max(ret, go(now + 1, cap)); // 기존의 dp[now][cap]의 무게와 비교하여 최대 가치를 dp에 저장해줍니다.
return ret;
}
int main()
{
cin >> n >> k;
memset(dp, -1, sizeof(dp));
for (int i = 1; i <= n; i++)
cin >> w[i]>>v[i]; // 무게와 가치를 입력받습니다.
cout << go(1,k); // 첫번째 인덱스부터 시작했습니다.
return 0;
}