[JAVA]백준_12865_평범한 배낭

문제링크

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

12865번: 평범한 배낭

 

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

public class Main {

	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 [] weights = new int[N+1];
		int [] profits = new int[N+1];
		int [][] D = new int[N+1][K+1];
		
		for(int i=1;i<=N;i++) {
			st = new StringTokenizer(br.readLine());
			weights[i] = Integer.parseInt(st.nextToken());
			profits[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i=1;i<=N;i++) { //첫번째 물건 부터 고려해서
			for(int k=1;k<=K;k++) {//무게는 1부터 고려
				if(weights[i]<=k) {
					D[i][k] = Math.max(D[i-1][k-weights[i]]+profits[i], D[i-1][k]);
				}
				else {
					D[i][k] = D[i-1][k];
				}
			}
		}
		
		System.out.println(D[N][K]);
	}
}

 

 

물건이 N개 있다는 가정하에 1번째 물건을 넣고 안넣고,2번째 물건을 넣고 안넣고,,, N번째 물건을 넣고 안넣고 식으로 고려하면 전체 2의N제곱만큼 수행하게 되어 수가 기하급수적으로 커진다.

따라서 dp를 사용하여  해결하여야한다. 이렇게 풀 경우 물건의 개수 N * 물건의 무게 W만큼 수행되어진다.

배열을 D[N+1][W+1]만큼 선언하여주고 시작하겠다.

첫번째 물건부터 고려해본다.

무게는 1~K까지 고려한다. 

만약 현재 무게에 첫번째 물건이 들어갈 수 있는 경우

현재 물건을 넣을 경우 D[i-1][k-weights[i]]+profits[i]

넣지 않을 경우 D[i-1][k] 중 큰 값을 현재 배열에 넣어준다.

만약 현재 무게에 첫번째 물건이 들어갈 수 없는 경우에는 직전에 누적된 값을 현재 배열에 넣어준다.