05.13. 평범한 배낭 [Dynamic Programming][백준 12865]

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

12865번: 평범한 배낭

 

Algorithm classification : Dynamic Programming, Knapsack Problem

 

05.13.1. Problem

This is a very mediocre backpack problem.

Jun-seo, who receives a national call in a month, is about to go on a trip. Since it is a trip to enjoy as much as possible while mourning the break from the world, we also try to pack a backpack as valuable as possible.

There are N items that Jun-seo thinks is necessary for the trip. Each object has a weight W and a value V, and if you put the object in a backpack, Junseo can enjoy it as much as V. Jun-seo, who has never marched, can only carry a backpack that can hold a maximum weight of K. In order to make the trip as enjoyable as possible for Jun-seo, let us know the maximum value of the items that can be put in the backpack.

 

05.13.2. Input limit

The first line gives the number of items N (1 ≤ N ≤ 100) and the weight K (1 ≤ K ≤ 100,000) that Junseo can withstand. From the second line to N lines, the weight W (1 ≤ W ≤ 100,000) of each object and the value V (0 ≤ V ≤ 1,000) of the object are given.

All numbers given as inputs are integers.

 

05.13.3. Output

Prints the maximum value of the sum of values ​​of items that can be put in a backpack in one line.

 

05.13.4. Solution

P & NP Problem에 대해 알고리즘 교과목 시간에 배우셨다면 익숙할 문제입니다. 유명한 NP-hard 문제 중 하나로 물품을 순서대로 넣을지 말지 결정하는 문제입니다. 

int n, k;
int a[102][2]= {0};
int dp[101][100010] = {0}; 

int main()
{
	scanf("%d %d", &n, &k);
	
	int i, j;
	for(i = 1; i <= n; i++){
		scanf("%d %d", &a[i][1], &a[i][0]); // w, v 
	}
	
	for(i = 1; i <= n; i++)
    {
        int w = a[i][1], v = a[i][0];
        for(j = 0; j <= k; j++)
        {
            if(j < a[i][1]) dp[i][j] = dp[i-1][j];
            else dp[i][j] = max(dp[i-1][j], dp[i-1][j - w] + v);
        }
    }
	
	printf("%d", dp[n][k]);
	
	return 0;
}

배낭의 빈 공간이 물품을 넣기 충분한지 살피면 됩니다. Top-down방식으로 해결한다면 해당 turn까지 고려한 물품의 index와 배낭의 빈공간을 argument로 넘기면 됩니다. 남은 물품을 넣으면서 구할 수 있는 최대 가치 합을 return 시켜주면 됩니다.

 

max(DP function(i + 1, limit), DP function(i + 1, limit - W_i) + V_i)

 

부분문제에서는 물품을 넣을지 말지 결정만 하기 때문에 O(NV)의 시간복잡도를 가집니다. N & NP Problem에 대해서는 조금 더 설명할 기회가 있으면 좋을텐데요. NP-hard 문제가 어떻게 다항함수의 시간복잡도를 가질 수 있는지 궁금하실텐데요. 이런 시간복잡도를 pseudo-polynomial time이라고 표현합니다. 주어진 input의 값에 대한 다항시간이라는 의미이죠. 엄밀한 polynomial time은 input의 bit length에 대한 다항시간을 의미합니다. 이렇게 NP-hard 문제 중 pseudo-polynomial time에 해를 구하는 알고리즘이 존재하는 문제를 weakly NP-hard class로, 구할 수 없음이 증명된 문제들을 strongly NP-hard class로 분류하기도 합니다. 

 

이 내용에 대해 조금 더 알아보고 싶은 분들은 The Design of Approximation Algorithms

The Design of Approximation Algorithms | Algorithmics, complexity, computer algebra and computational geometry

을 참고해보시는 것도 좋을 것 같습니다.(Online pdf는 https://www.designofapproxalgs.com/index.php 에서 확인하실 수 있습니다.) 한글로 된 문서를 찾으신다면 https://gazelle-and-cs.tistory.com/51

[배낭문제 / Knapsack Problem] 다항 시간 근사 해법 (PTAS)

를 참고하시면 좋을 것 같습니다. 무슨 말인지 아직 이해하진 못하겠지만 조금 더 높은 수준의 문서를 원하신다면

https://s-space.snu.ac.kr/bitstream/10371/5341/1/24.%20%EC%9D%BC%EB%B0%98%EB%B0%B0%EB%82%AD%EB%AC%B8%EC%A0%9C%EC%9D%98%20%EC%99%84%EC%A0%84%EB%8B%A4%ED%95%AD%EC%8B%9C%EA%B0%84%EA%B7%BC%EC%82%AC%ED%95%B4%EB%B2%95%EA%B5%B0%EC%9D%98%20%EC%A1%B4%EC%9E%AC%EC%A1%B0%EA%B1%B4.pdf

도 괜찮을 것 같습니다.