[Baekjoon] 12865번: 평범한 배낭

 

 

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

---

 

문제 해결 과정

착안

배낭에 넣고자 하는 물건의 무게의 총합이 $k \space (1 \leq k \leq K)$일 때, 같은 무게로 만들 수 있는 가치의 총합 중 가장 큰 값을 배열에 저장하기 위해 동적계획법을 사용하여 문제를 해결하고자 하였다.

 

$i$번째 물건의 무게를 $w_i$, 가치를 $v_i$라고 하면, $1, 2,\cdots, i$번째 물건을 배낭에 넣기 위해서는

$$\sum_{1}^{i} w_i \leq K$$

를 만족해야하므로, $1, 2, \cdots, i$번째 물건들의 무게의 총합 $k$에 대한 가치의 총합을 저장하는 배열 $DP[k]$의 값을 아래와 같이 갱신할 수 있다.

 

• $k = w_i$인 경우: $DP[k] = DP[0] + v_i = v_i$
• $k > w_i$인 경우: $DP[k - w_i] > 0$인 경우, $DP[k]$의 값과 $DP[k - w_i] + v_i$의 값 중 큰 값으로 갱신.

 

구현

위의 알고리즘에 따라 구현할 때 주의할 점은, 물건 한 종류 당 한 번씩만 배낭에 넣을 수 있기 때문에 물건의 가치를 중복하여 계산하지 않아야 한다. 따라서, 넣고자 하는 물건의 무게의 총합 $k$에 대한 반복문을 뒤에서부터 거꾸로 돌아야한다는 점에 유의하여 프로그래밍 하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <algorithm>

using namespace std;

struct Item
{
	int W;
	int V;
};

Item Items[100];
int DP[100001];

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

	for (int i = 0; i < N; i++)
		cin >> Items[i].W >> Items[i].V;

	for (int i = 0; i < N; i++)
		for (int k = K; k >= Items[i].W; k--)
			if (k == Items[i].W || DP[k - Items[i].W] > 0)
			{
				int valueSum = DP[k - Items[i].W] + Items[i].V;
				if (DP[k] < valueSum)
					DP[k] = valueSum;
			}

	cout << *max_element(DP, DP + K + 1) << "\n";
	return 0;
}

 

실행 결과