C++) [BOJ] 12865 평범한 배낭 ★ 0/1 Knapsack Problem, Dynamic Programming

12865번: 평범한 배낭 (acmicpc.net)

12865번: 평범한 배낭

 

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

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

// 점화식 max(DP[i-1][j], DP[i-1][j-W[i]])

int main()
{
	cin >> N >> K;

	for (int i = 1; i <= N; i++) 
	{
		cin >> W[i] >> V[i];
	}
	
	// 물건 번호
	for (int i = 1; i <= N; i++)
	{
		// 물건 무게
		for (int j = 1; j <= K; j++)
		{
			// 배낭의 무게가 j일 때 현재 물건(W[i])가 가방에 들어간다면
			if (j - W[i] >= 0) 
			{
				// 전 열의 값과 현재 배낭의 무게와 
				// 물건의 무게를 뺀 열의 값과 현재 물건의 값을 더한 값 중 더 큰 값을 저장한다.
				DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i]);
			} 
			// 배낭의 무게가 j일 때 현재 물건(W[i])가 가방에 들어가지 않는다면
			else 
			{
				// 전 열의 값을 그대로 저장한다.
				DP[i][j] = DP[i - 1][j];
			} 
		}
	}

	cout << DP[N][K];
}

 

 알고리즘의 구현이 실제 배낭에 물건을 넣는 방법과 다르게 구현되기 때문에 알고리즘 공식을 숙지하고 문제 유형을 파악할 수 있어야 문제를 풀 수 있다.

 

참조

https://cocoon1787.tistory.com/206

[C/C++] 백준 12865번 - 평범한 배낭 (DP, Knapsack 알고리즘)