백준 12865번 _ 평범한 배낭

2020-05-10 · 배운 것 · 2분 읽기

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

12865번: 평범한 배낭

풀이방법

그냥 냅색 알고리즘이다.

dp[가방종류][무게] = 가질수있는 최대가치
이렇게 dp를 설정해두고, dp[i][j] = max(dp[i][j] = max(dp[i][j], dp[i - 1][j - weight] + value) 이 점화식을 이용해 풀면된다.

for (int i = 1; i <= N; i++)
{
	int weight = W[i];
	int value = V[i];
	for (int j = 1; j <= K; j++)
	{
		dp[i][j] = dp[i - 1][j];

		if (j - weight >= 0)
			dp[i][j] = max(dp[i][j], dp[i - 1][j - weight] + value);
	}
}

전체코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int dp[101][100001];
int W[101];
int V[101];
int N, K;

void Input()
{
	cin >> N >> K;
	for (int i = 1; i <= N; i++)
	{
		cin >> W[i] >> V[i];
	}
}

void solve()
{
	for (int i = 1; i <= N; i++)
	{
		int weight = W[i];
		int value = V[i];
		for (int j = 1; j <= K; j++)
		{
			dp[i][j] = dp[i - 1][j];

			if (j - weight >= 0)
				dp[i][j] = max(dp[i][j], dp[i - 1][j - weight] + value);
		}
	}
	cout << dp[N][K];
}

int main()
{
	Input();
	solve();

	return 0;
}

후기

4달전에 풀었던 dp문제인데 다르게 dp 일차원 배열로 풀려다가 머리아파서 그냥 똑같은 방식으로 풀었다. 이게 메모리를 더 많이 잡아먹긴하지만 구현하긴 쉬운것같다.ㅎ