[BOJ 12865번] 평범한 배낭(JAVA)

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

12865번: 평범한 배낭

//knapsnack 알고리즘
import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	static int[] w, v;
	static int[][] d;
	
	public static void main(String args[]) throws Exception {
		String s[]=br.readLine().split(" ");
		int n=Integer.parseInt(s[0]);
		int k=Integer.parseInt(s[1]);
		w=new int[n+1];
		v=new int[n+1];
		d=new int[n+1][k+1];
		for(int i=1;i<=n;i++) {
			String s2[]=br.readLine().split(" ");
			w[i]=Integer.parseInt(s2[0]);
			v[i]=Integer.parseInt(s2[1]);
		}
		
		for(int i=1;i<=n;i++) {
			for(int j=0;j<=k;j++) {
				d[i][j]=d[i-1][j];
				if(j>=w[i]) {
					d[i][j]=Math.max(d[i][j], d[i-1][j-w[i]]+v[i]);
				}
			}
		}
		bw.write(String.valueOf(d[n][k]));
		bw.flush();
		bw.close();
	}
}

 이 문제는 찾아보니 knapsnack 알고리즘 문제라고 합니다.

도둑이 보석을 훔쳐가려고 할 때 최대 무게가 정해져 있는 가방에 보석을 담았을 때 보석의 합이 최댓값이 되도록 하는 알고리즘입니다.

위 문제에서 정수 배열인 w와 v를 선언하고, w에는 물건의 무게와 v에는 물건의 가치를 저장했습니다.

이후 정수 이중배열 d를 선언합니다.

d[i][j]라 할 때 i는 가져가야하는 보석의 인덱스 번호(i번째 보석), j는 가방에 담을 수 있는 남은 무게고, d는 현재 가방에 담겨져 있는 가치의 합입니다.

1번째 보석부터 n번째 보석까지 for문을 이용해서 살펴보고, 만약 i번째 보석의 가치<가방에 담을 수 있는 남은 무게(j>=w[i])아면 d[i][j]=에 d[i][j]와 d[i-1][j-w[i]]+v[i] 중 큰 값을 넣어서 d[n][k]값까지 값을 이동시킵니다.