[백준] 단계별로 풀어보기(단계:15,동적계획법1,JAVA)12865번, 평범한 배낭

문제 링크

12865번: 평범한 배낭

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적계획법이란 위 문제와 같이 동일한 연산을 계속 반복하여 비효율적으로 코드가 실행되어 그것을 향상시키기 위하여반복되는 연산의 결과를 따로 저장하여 적재적소에 코드가 더 효율적으로 만드는 방법입니다.

 

배낭에 물건을 넣을 때에 최대의 가치를 넣을 때를 표로 만들었습니다.

표에서 열의 index값은 무게의 최대 무게일 때를 표현합니다.

예를 들어 index=4이면 최대무게가 4일 때 배낭에 넣을 수 있는 물건의 최고의 가치를 표현하는 것입니다.

표에서 행의 index값은 입력값에서 받은 무게 값에 대응하여 그 물건 이하의 물건들로 가치값을 구하는 것입니다.

예를 들어 index=3이면 3번째 입력되었던 무게 3이 대응되고 그 이하의 물건으로 무게가 6, 4, 3인 물건들로 최대의 가치값을 만들어 표에 작성한 것입니다.

예제 입력 1에 대한 표를 만들면

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
6	0	0	0	0	0	0	13	13
4	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
5	0	0	0	6	8	12	13	14

 

예를 들어 (3, 7)에 값을 구할 때에는 최대무게=7 배낭의 물건은 무게= 6, 4, 3인 물건들로 가치의 최대값을 구한 것입니다. 무게 4인 물건과 무게 3인 물건을 넣는 것으로 6 + 8으로 14가 최대값이 된 것입니다.

 

또다른 예로 (1, 3)이면 최대무게 = 3 배낭의 물건은 무게 = 6인 물건들로 가치의 최대값을 구하는 것으로 하나 뿐인 물건이 최대무게보다 크기 때문에 들어가지 못하여 가치는 0으로 표시됩니다.

 

표에 값들을 살펴보면 규칙을 발견할 수 있습니다.

 

만약 물건의 무게가  최대무게보다 클 경우  : 같은 열의 (행－1)의 값

 

예를 들어 (4, 3)은 해당 물건의 무게 5는 최대 무게 3보다 커서 (3,3)의 값 6이 저장됩니다.

 

이유 : 해당 물건은 들어가지 못하므로 그 이외에 물건들에서 가치의 최대값을 넣어야 하므로 같은 열의 (행-1)의 값은 그 이외의 물건들에서 넣을 수 있는 최대값을 표시하는 값이기 때문입니다.

 

그 이외에 경우 : Math.max(해당 물건 들어가지 않았을 때 가치 최대값, 해당 물건 들어갔을 때 가치 최대값)

 

예를 들어 (3, 7)은 우선 해당 물건의 무게는 3으로 최대무게보다 작아서 배낭에 들어갈 수 있습니다. 그래서 물건이 들어가지 않았을 때는 (2, 7)이고 물건이 들어갔을 경우 해당 물건 가치와 남은 무게에 대한 최대 가치값으로 6 + (2, 4)의 값이 됩니다. (2, 7) = 13 , (2, 4) = 8로 13<14가 더 크므로 해당 물건이 들어갔을 때 가치값(14)이 더 크다.

 

이유 : 해당 물건이 최대무게보다 작기 때문에 배낭에 들어갈 수 있습니다. 그래서 해당 물건이 들어갔을 때에 최대값과 들어가지 않았을 때에 최대값을 구하여 더 큰 최대값을 표시하는 것입니다.

 

해당 물건이 들어가지 않았을 때 : 같은 열의 (행-1)의 값

 

해당 물건이 들어갔을 때 : 해당 물건의 가치 + 열은(전체 무게 - 해당 물건의 무게)이고 행에 -1의 값

 

행을 -1을 하는 이유는 같은 최대무게에 해당 물건을 제외한 물건을 표현하는 것이기 때문입니다.

 

예를 들어 (3, 2)는 무게가 6, 4, 3인 물건들이 최대무게 2일때 들어가는 것이지만 (2, 2)는 무게가 6, 4인 물건들이 최대무게 2일때 들어가는 것으로 (행-1)을 하면 해당 무게 3을 제외한 물건들에 최대값을 얻을 수 있습니다.

 

최대무게와 물건을 넣을 수 있는 개수에 따라 가치의 최대값을 저장하기 위해  [물건수+1][최대무게+1]로 배열의 메모이제이션을 구성하였습니다.

• 최대무게와 물건을 넣을 수 있는 개수에 따라 가치의 최대값을 저장할 메모이제이션 배열 check를 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 사용하여 입력값을 띄어쓰기 나누어 무게와 가치를 2차원 배열 weight에 저장하였습니다.
• 최대무게와 물건에 따른 가치 최대값을 계산하는함수 bag을 만들었습니다.
• 2중 for문을 통해서 모든 경우의 수에 대한 bag에 값을 메모이제이션에 저장하였습니다.
• 메모이제이션[index][maxWeight]값이 넣을 수 있는 최대값을 System.out.println을 사용하여 출력하였습니다.

• 메모이제이션이 0인 경우는 그 수의 연속합이 저장되어 있지 않다고 판단하여 재귀를 실행
• check가 0이 아니면 탐색된 값이기 때문에 넘어갑니다.
• 위에 알고리즘처럼 작동하게 bag함수를 작성하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int[][] check;	//메모이제이션 배열
	static int[][] weight;	//무게 및 가치 저장 배열
	static int index;		// 물건 개수
	static int maxWeight;	// 무게 최대치
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
        //---------입력값 저장 및 배열 초기화------------
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	index = Integer.parseInt(st.nextToken());
    	maxWeight = Integer.parseInt(st.nextToken());
    	check = new int[index+1][maxWeight+1];
    	weight = new int[index+1][2];
    	for(int i=1;i<=index;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		weight[i][0] = Integer.parseInt(st.nextToken());
    		weight[i][1] = Integer.parseInt(st.nextToken());
    	}
        //--------------함수 실행-----------
    	for(int i=1;i<=maxWeight;i++)
    		for(int j=1;j<=index;j++)
    			bag(i,j);
    	
    	System.out.println(check[index][maxWeight]);	//결과 출력
    	br.close();
	}
    //--------배낭에 넣을 수 있는 최대 가치 구하는 함수--------------
	public static void bag(int w, int i) {
		if(check[i][w]==0) {
			if(weight[i][0]>w)	//최대무게보다 클 경우
				check[i][w] = check[i-1][w];	//같은 열의 (행-1)의 값
			else		//그 이외에 경우
				check[i][w] = Math.max(check[i-1][w], 
                check[i-1][w-weight[i][0]] + weight[i][1]);
                //Math.max(해당 물건 들어가지 않았을 때 가치 최대값, 해당 물건 들어갔을 때 가치 최대값)
		}
	}
}