[C] 백준 - 12865번: 평범한 배낭

7월 17일(월) - 다이나믹 프로그래밍 (12865번)

12865번: 평범한 배낭

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- dp방식을 이용한 풀이를 예상함

- N개의 물건들 각각의 무게w와 가치v를 가지고 하나하나 비교하며, 최대무게인 K를 넘는지를 확인해야하므로

  MAX 매크로를 추가해야할듯

- MAX ( i번째 새로운 물건을 넣기 전, i번째 새로운 물건을 넣은 후 ) 를 비교한 값을 dp[ i ]로 반복문을 통해 돌린다

- 최종출력은 N개의 물건 모두의 넣었다 / 뺐다를 진행하고 난 이후의 값인 dp[N]

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

1. 최초 생각처럼 dp방식을 이용하는 것을 예상했지만, 1차원 배열만으로 생각해서는 더 이상의 풀이 진행이 불가

-> 아래 링크 게시물의 초반부분을 통해서 2차원 배열을 사용한 dp방식을 생각할 수 있었다

-> 또한 dp중에서도 Knapsack 알고리즘을 따로 정리해놓을 정도로 다양한 활용이 가능하다는 점도 알게되었다

[알고리즘 트레이닝] 5장 - 동적계획법과 냅색(Knapsack) (백준 12865번 평범한 배낭 문제로 살펴보기)

-> 따라서 N개의 물건들의 무게와 가치는 각각 w[101] 과 v[101]에 입력받는다

-> dp[ i ][ j ]는 처음부터 i번째까지의 물건을 살펴보았고, 배낭의 현재 사용가능한 용량은 j이며,

    이때 물건 가치합의 최댓값을 뜻하게된다

-> 그러므로 이중 for문 안에서

    1) 만약 i번째 물건을 가방에 넣을 수 있다면, i번째 물건을 가방에 넣기 전과 넣은 후

        두 개의 값 중 더 큰 값을 dp에 저장한다

    2) 만약 i번째 물건을 가방에 넣을 수 없다면, 직전 dp값인 dp[ i-1 ][ j ] 값을 그대로 dp[ i ][ j ]에 저장

-> 최종출력은 dp[N][K]

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#define MAX(x, y) (((x) > (y)) ? (x) : (y))

#include <stdio.h>

int dp[101][100001];
int w[101];
int v[101];

int main(void)
{
	int N, K;
	scanf("%d %d", &N, &K);

	for (int i = 1; i < N + 1; i++)
	{
		scanf("%d %d", &w[i], &v[i]);
	}

	for (int i = 1; i < N + 1; i++)
	{
		for (int j = 1; j < K + 1; j++)
		{
			if (j - w[i] >= 0)
			{
				dp[i][j] = MAX(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
			}
			else
			{
				dp[i][j] = dp[i - 1][j];
			}
		}
	}

	printf("%d", dp[N][K]);
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ