[BJ] 12865. 평범한 배낭.java

1. 1차원 dp[] 를 사용한 방법

1. dp[] 배열을 만들기

2. 6 13 (→ 6kg에 13의 가치를 가지는 물건이 들어옴)

3. 4 8 (→ 4kg에 8의 가치를 가지는 물건이 들어옴)

4. 3 6 (→ 3kg에 6의 가치를 가지는 물건이 들어옴)

→ 이전에 7kg의 가방은 13의 가치를 가지는 물건을 가지고 있었지만 4kg의 물건과 새로 들어온 3kg의 물건을 더하면 14의 가치를 가지므로 dp[7]의 값을 변경해준다.

5. 5 12 (→ 5kg에 12의 가치를 가지는 물건이 들어옴)

• 코드
  

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

public class 12865_평범한배낭 {
	public static int N,K; // 물품의 수 N, 준서가 버틸 수 있는 무게 K
	public static int dp[];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		String[] str = br.readLine().split(" ");
		N = Integer.parseInt(str[0]);
		K = Integer.parseInt(str[1]);
		
		dp = new int[K+1];
		
		int w, v; // 물건의 무게 w, 물건의 가치 v;
		for(int i =0; i<N; i++) {
			str = br.readLine().split(" ");
			w = Integer.parseInt(str[0]);
			v = Integer.parseInt(str[1]);
			
			int value, cost;
			for(int j = K; j>=w; j--) {
				value = j - w; 
				cost = v + dp[value];  
				if(cost > dp[j]) { // w의 가치 + w를 제외한 나머지 무게의 가치 > j의 가치
					dp[j] = cost;
				}
			}
		}
		System.out.println(dp[K]);
	}
}

• 결과
  

---

2. 2차원 dp[][] 를 사용한 방법

(w,v) : 물건의 무게, 물건의 가치 → Ex) (6,13) 6kg의 물건은 13의 가치를 가진다.

가방을 순차적으로 비교해서 dp[][]를 갱신한다.

📌 주의! 가방에 물건을 넣고 시작하는게 아니라 다른 가방들에 자신의 물건을 넣을 수 있는지 확인하고 제일 마지막에 자신의 물건과 무게가 같은 가방에 물건을 넣을 수 있는지 확인한다. 따라서 2차원 배열의 각 행을 탐색하는 경우에는 for문을 이용하여 뒤에서부터 탐색을 시작한다.

• 코드

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

public class 12865_평범한배낭 {
	public static int N,K; // 물품의 수 N, 준서가 버틸 수 있는 무게 K
	public static int dp[][];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		String[] str = br.readLine().split(" ");
		N = Integer.parseInt(str[0]);
		K = Integer.parseInt(str[1]);
		
		dp = new int[N+1][K+1];
		
		int w, v; // 물건의 무게 w, 물건의 가치 v;
		for(int i =1; i<=N; i++) {
			str = br.readLine().split(" ");
			w = Integer.parseInt(str[0]);
			v = Integer.parseInt(str[1]);
			
			for(int j=0; j<K+1; j++) {
				dp[i][j] = dp[i-1][j];
			}
		
			
			int cost;
			for(int j = K; j>=w; j--) {
				cost = v + dp[i-1][j-w];
				if(cost > dp[i-1][j]) {
					dp[i][j] = cost;
				}
			}
			
		}
		System.out.println(dp[N][K]);
	}
}

• 결과