백준 12865 C++ - 평범한 배낭

Intro

문제해결 및 소스코드

#include <iostream>
#include <algorithm>

using namespace std;

/*									<문제해결>
				배낭문제는 대표적인 DP 알고리즘 문제이다.

				이 문제에서 중요한점은, 물품이 하나씩 늘어날때마다 달성할 수 있는 최대가치가 달라지게되는데,
				이것을 어떻게 업데이트해줄것인가 이다.
				
				예제1) 물품1[무게6, 가치13] 물품2[무게4, 가치8] 물품3[무게3, 가치6] 물품4[무게5, 가치12] 
                       배낭의 최대무게는 7

                첫번째 물품만 있을때, 배낭에 넣을 수 있는 최대가치는 물품1을 넣은 13이다. 그리고 여유무게 1이 남는다.

                두번째 물품까지 있을때, 배낭에 넣을 수 있는 최대가치는 물품1을 넣은 13이다. 여유무게 1이 남는다.

                세번째 물품까지 있을때, 배낭에 넣을 수 있는 최대가치는 물품2와 물품3을 넣은 14이다.

                네번째 물품까지 있을때, 배낭에 넣을 수 있는 최대가치는 물품2와 물품3을 넣은 14이다.

                물품이 추가되었을 때, 우리는 이 추가된 물품을 넣을지 말지를 결정해야한다.
                넣는 경우는 기존보다 더 높은 가치를 달성할 수 있을때 일것이다.

                따라서 이문제에서는 세번째 물품이 입력됐을때, 기존 최대가치이던 물품1만넣은 13이,
                이제는 세번째물품을 넣고나니 여유무게4가 남아서 두번째물품까지 넣었을 때의 가치 14가 기존의 가치보다 높아졌으니 물품2,3을 넣는것이 가치의 최댓값이 된다.
*/

int dp[101][100001];			// dp[i][j] : i번째 물건까지에서, 배낭에 최대jKg까지 담을 때 최대가치
int W[101];						// i번째 물건의 무게
int V[101];						// i번째 물건의 가치

int main()
{
	int n, k;
	cin >> n >> k;

	// 입력
	for (int i = 1;i <= n;i++)
	{
		cin >> W[i] >> V[i];
	}

	// dp[0] : 0으로 초기화됨

	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= k;j++)
		{
			// 물건을 넣을 수 있는경우
			if (j >= W[i])
                // 이전의 최대가치가 큰지, 이 물품을넣고 여유무게에 다른물품을 더 넣는게 큰지
				dp[i][j] = max(dp[i - 1][j - W[i]] + V[i], dp[i - 1][j]);
			// 물건을 넣을 수 없는경우
			else
				dp[i][j] = dp[i - 1][j];    // 이전의 최대가치를 그대로
		}
	}

	cout << dp[n][k];
}