백준 12865 평범한 배낭 C++

기본 접근법 : 2차원 DP

전통적인 배낭 문제의 해결 방법은 2차원 DP 배열을 사용하는 것

for (int i = 1; i <= N; i++)
{
	for (int j = 1; j <= K; j++)
	{
		if (j >= Weight[i])
		{
			DP[i][j] = Max(DP[i - 1][j], DP[i - 1][j - Weight[i]] + Value[i]);
		}
		else
		{
			DP[i][j] = DP[i - 1][j];
		}
	}
}

• DP[i][j]는 i번째 물건까지 고려했을 때, 배낭 용량이 j일 때의 최대 가치
• 각 물건마다 두 가지 선택지는 물건을 넣거나, 넣지 않거나
• j >= Weight[i]일 경우, 물건을 넣을 수 있으므로 두 선택지 중 더 나은 것을 선택
• 그렇지 않은 경우, 물건을 넣을 수 없으므로 이전 상태를 유지

최적화된 접근법 : 1차원 DP

공간 복잡도를 최적화한 1차원 DP 배열을 사용

vector<int> dp(maxWeight + 1, 0);
for (int i = 0; i < N; ++i)
{
    int W = 0, V = 0;
    cin >> W >> V;
    for (int weight = K; weight >= W; --weight)
    {
        dp[weight] = max(dp[weight], dp[weight - W] + V);
        answer = max(answer, dp[weight]);
    }
}

• 현재 아이템을 넣을 수 있는 무게들에 아이템의 가치를 갱신
• 같은 물건을 여러 번 선택하는 것을 방지하기 위해 무게를 K부터 현재 물건의 무게까지 역방향으로 반복

두 접근법의 차이

1. 메모리 사용량
   • 2차원 DP: O(N×K) 메모리 사용
   • 1차원 DP: O(K) 메모리 사용
2. 코드 간결성
   • 1차원 DP가 더 간결하고 배열 초기화 및 구현이 단순