140. 12865(평범한 배낭)

import java.util.*;
import java.io.*;

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmp1 = br.readLine().split(" ");
		int N = Integer.parseInt(tmp1[0]);
		int K = Integer.parseInt(tmp1[1]);
		int[][] DP = new int[N + 1][K + 1];

		for (int i = 1; i <= N; i++) {
			String[] tmp2 = br.readLine().split(" ");
			int weight = Integer.parseInt(tmp2[0]);
			int value = Integer.parseInt(tmp2[1]);

			for (int j = 1; j <= K; j++) {
				if (j < weight) {
					DP[i][j] = DP[i - 1][j];
				} 
				
				else {
					DP[i][j] = Math.max(value + DP[i - 1][j - weight], DP[i - 1][j]);
				}
			}
		}
		
		System.out.println(DP[N][K]);

	}
}

 

문제요약

군대가기전 여행가는 준서의 배낭을 최대한 가치있게 준비할 수 있도록 하자. 

설명

첫줄에 K는 무게이다.

두번째 줄 부터 첫번째 인덱스 값이 무게이다.

 

무게 0~K까지 증가시키면서 두번째 줄부터 들어오는 물건의 무게와 가치를 비교한다.

DP i 인덱스의 0~K 무게(j) 는 각 무게에서 가장 높은 가치를 지닌 것이라고 생각하면 된다.

 

전의 무게와 , 현재 새로 갱신하는 무게를 비교해 보았을 때 더 큰 무게를 저장하면된다.

 

다음 과 같이 입력이 4 8일때 최대 4kg를 지닐 수 있다면 8의 가치가 최대이다.

하지만 최대 지닐 수 있는 무게가 6kg 일 때 4kg을 지니고 가는 것 보다는 6kg을 지니고 가는게 더 가치가 높다.

 

따라서 

DP[i][j] = Math.max(value + DP[i - 1][j - weight], DP[i - 1][j]);

다음과 같이 새로 갱신하는 무게와 전의 무게중 더 큰 것을 비교해서 저장하면 된다.

현재 j무게에서 weigth을 빼주는 이유는 , value를 더하게 된다면 남은 j-weight만큼 무게가 남을 것이고, 그 인덱스에 해당하는 무게를 더해주어 무게를 가지고 계산할 수 있는 가장 큰 값을 만들 수 있다.

위 공식으로 DP[전 인덱스][남은 무게의 값]의 가치와 현재 가치를 더해 최대 가치를 만들 수 있다.