백준 12865번: 평범한 배낭 (C++)

 

문제 링크 : www.acmicpc.net/problem/12865

 

 

 

다이나믹 프로그래밍 문제이다. (knapsack 문제) 

 

 

 

<전체적인 알고리즘>

1. 특정 아이템을 넣을지 말지의 경우를 모두 저장하며 구해나간다.

    - 아이템 마다 결정할 때 가방의 무게가 w ~ k일 때의 모든 경우를 저장하여야 한다.

       (w미만은 어차피 넣을 수 없으니 고려할 필요가 없음)

2. 마지막 아이템까지 다이나믹 프로그래밍을 진행하면 결국 가방 무게가 k일때의 d[k]값이 정답이다.

 

 

 

<부가적 설명>

- knapsack문제를 2차원 배열에 저장하며 계산한다면 좀 더 이해하기 직관적일 것이다. 하지만 메모리를 아끼기 위해 1차원 배열로 알고리즘을 구현하였다.

- 1차원 배열을 이용한다면 배열을 계속 갱신할 때 뒤에서 부터 갱신하여야 한다. 뒤에서 부터 갱신하여야 그 전의 값들을 사용할 수 있기 때문이다.

 

 

 

<전체 코드>

#include<iostream>
#include<algorithm>

using namespace std;

int item[102][2]; // 0 -무게 / 1- 가치
int d[100002];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, k;
	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		int w, v;
		cin >> w >> v;       //각 아이템의 무게와 가치 입력
		
		for (int j = k; j >=w; j--)  // 가방 용량이 w ~ k 인 경우 전부 구하기
		{
			d[j] = max(d[j - w] + v, d[j]);  //item을 넣었을 때와 넣지 않은 것중 가치 큰 값 저장
		}
	}

	cout << d[k];  // 가방무게가 k일 때 가치의 최대 값

	return 0;
}

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.