[백준][12865]평범한 베낭

/* 문제설명 */

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

 

 

 

 

---

 

 

 

/* 풀이방법 */

이문제는 아~주 유명한 Knapsack algorithm을 사용해서 풀어야 한다.

베낭 알고리즘은 두가지 종류가 있는데,

물품을 쪼갤수 있는 Fraction Knapsack problem과 물건을 쪼갤 수 없는 0/1 Knapsack problem으로 나뉜다.

Fraction Knapsack problem는 그리드 알고리즘을 활용해야 하며, 0/1 Knapsack problem는 DP로 풀어야한다.

위의 문제는 물건을 쪼갤 수 없으므로 DP로 풀어야 한다..

 

자 그럼 최대 이윤을 배열에 저장해 가면서 풀어보자.

일단 최대 이윤을 저장하기 위해 아래와 같은 표를 만들었다.

여기서 아이템들은 백준문제의 예시를 그대로 사용했다.

아이템1은 무게 6, 가치 13 

아이템2는 무게 4, 가치 8

아이템3은 무게 3, 가치 6

아이템4는 무게 5, 가치 12를 지닌다.

 

 

 

 

 

이제 값을 저장해보자..

나는 나중에 코드 짤때, 범위인지 아닌지 알아내는거 쓰기 귀찮아서 위에 0번째 줄을 제로패딩 해줬다.

아이템1은 무게 6, 가치 13를 지닌다는 점을 생각하면서 채우자

 

 

 

 

 

 

 

일단 여기까지는 무난하게 진행된다. 이제 무게가 6kg면 아이템1은 담는게 가능하므로 저칸에 최고 가치인 13을 쓰게 된다.

 

 

 

 

 

 

자 그리고 옆칸도 무게 7에 아이템1만 있을 경우의 최고 가치이므로 당연히 13이 될 것이다.

 

 

 

 

 

 

 

이런식으로 다음줄도 채워보겠다. 아이템2는 무게 4, 가치 8을 지닌다.

 

 

 

 

 

 

 

사실 이때부터 비교해 주어야 할칸이 총 세칸이다.

일단 (2,5)에 위치한 초록색 칸이 의미하는 바에 대해 다시 생각해 봐야한다.

무게 제한이 5kg일때, 아이템 1,2만 가지고 가질수있는 최대 가치를 표현해야한다.

그러면 저 값을 위해 비교해야할 값은

첫째, 바로전 (2,4)에 위치한 연두색 칸이다. 해당 칸이 의미하는 바는 4kg제한에서 아이템 1,2만으로 가질수 있는 최대 가치이다. 1kg 늘어났다고해서 달라지는 바가 없을 수도 있지 않은가?

둘째, 바로위 (1,5)에 위치한 연두색 칸이다. 해당 칸이 의미하는 바는 5kg제한에서 아이템 1만으로 가질수 있는 최대 가치이다. 물건 하나 늘어났다고 해서 달라지는 바가 없을 수도 있지 않은가?

셋째는... 현재 아이템 무게를 뺀 가방에서 가질 수 있는 최고 가치와 현재 아이템의 가치를 더한 값이다.

해당 칸에서는 아이템2의 무게는 4이고 이번 문제에서 넣었던 물건은 또 넣을 수 없으므로, 

(1,1)에 위치한 주황색 칸에 있는 값이 최고 가치가 되는 것이다. 

이중 가장 큰값은 8 이므로 (2,5)에는 8을 입력하게 된다. 

 

사실 위와 같은 방법으로 계속 채워주면 된다.

 

 

 

 

 

 

 

 

 

자 채우고 채워서 여기까지 왔다.

사실 여기도 아까와 같은 방법으로 하면되는데, 다시한번 보겠다.

연두색 칸들이랑, 주황색칸 + 현재가치 중 가장 큰값을 택하면 된다.

지금 아이템3에 위치하고 있으므로 현재가치는 6. 따라서 6+8=14가 된다.

그럼 초록색 칸에는 가장 큰값인 14를 입력하게 된다.

 

 

다음줄도 마저 입력해보면..

 

 

 

 

 

 

이런 모양이 되고, 해당 예시에서 원하는 아이템 1,2,3,4를 가지고 7키로 제한의 가장 큰 가치는 (4,7)에 위치한 14가 되는것이다.

 

 

조만간 dp에 대해서도 한번 정리해야겠다는걸 많이 느꼈다..

 

 

 

 

---

 

/* 해답코드 */

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//평범한 베낭
public class b12865 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int[] w = new int[N+1];
		int[] v = new int[N+1];
		int[][] memo =new int[N+1][K+1];
		for(int i=1;i<=N;i++) {
			st = new StringTokenizer(br.readLine());
			w[i] = Integer.parseInt(st.nextToken());
			v[i] = Integer.parseInt(st.nextToken());
		}

		for(int i=1;i<=N;i++) {
			for(int j=1;j<=K;j++) {
				int pw = w[i];
				int pv = v[i];
				if(pw > j){
					memo[i][j] = memo[i-1][j];
	            }
	  			else{
	  				memo[i][j] = Math.max(memo[i-1][j], pv+memo[i-1][j-pw]);
	            }
			}
		}
		System.out.println(memo[N][K]);	
	}
}