[백준] 12865 평범한 배낭 - DP(Dynamic Programming) + 배낭문제(냅색, KnapSack) JAVA

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

12865번: 평범한 배낭

코드설명

DP에서 배낭문제(KnapSack) 알고리즘을 활용하여 진행합니다.

 

문제에서 

dp[N+1][K+1]] : N 번째 아이템에서 K 무게별로 최대의 무게를 저장합니다.

 

문제에서 

for(int i=1;i<=N;i++) { //몇번쨰 아이템인지를 의미합니다.
    for(int j=1; j<=K;j++) { // 무게를 의미합니다.
        dp[i][j] = dp[i-1][j]; //기본적으로 이전 아이템의 가치를 저장합니다.
        if( j - arr[i][0] >= 0 ) { //현재 무게에서 i번쨰 아이템의 무게 > 0 ( 즉, 본인 아이템을 담을 수 잇는지 확인 )
            dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - arr[i][0] ] + arr[i][1]);
        }
    }
}

• 우선 기본적으로 이전 아이템에서 해당 무게의 가치를 저장합니다. dp[i][j] = dp[i-1][j]; ( i번째 아이템의 j번째 무게일떄의 최대값에 i-1번쨰 아이템의 j일때의 최대값을 저장합니다. )
• 만약 i번쨰 무게에서 현재 무게의 값을 뺸 값이 양수라면, 해당 무게는 다른 배낭의 무게와 합쳐서 계산할 수 있다는 의미입니다.
  • dp[i][j] =  Math.max( dp[i-1][j], dp[i-1][j - arr[i][0] ] + arr[i][1] ) 를 통하여 더했을때의 값과 그대로의 값이 더 큰지 비교하여 갱신합니다.
  • 코드에서보면 j - arr[i][0] >= 0 인지 를 확인함으로써 해당 무게가 0 이상인지 확인하고 ( 즉, j번쨰 무게와 현재 무게를 뺐을때 0 이상이라는 의미는 이전에 들었었던 최대 dp[i-1][j-arr[i][0]] 에 현재 들고 있는 배낭의 무게인 arr[i][1]을 더할 수 있느냐,  2개를 들 수 있는가, 무게를 합칠 수 있는가 ), 그것의 무게를 dp[i-1][j - arr[i][0] ] 형태로 사용하는것을 볼 수 있습니다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.regex.Pattern;

public class Main {
	public static int N, K;
	public static String str;
	public static int[][] arr;
	public static int[][] dp; //각 무게별로 최대의 가치를 구합니다. 
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	K = Integer.parseInt(st.nextToken());
    	arr = new int[N+1][2];
    	dp = new int[N+1][K + 1]; 
    	
    	for(int i=1;i<=N;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i][0] = Integer.parseInt(st.nextToken()); //무게
    		arr[i][1] = Integer.parseInt(st.nextToken()); //가치
    	}
    	
    	for(int i=1;i<=N;i++) { //몇번쨰 아이템인지를 의미합니다.
    		for(int j=1; j<=K;j++) { // 무게를 의미합니다.
    			dp[i][j] = dp[i-1][j]; //기본적으로 이전 아이템의 가치를 저장합니다.
    			if( j - arr[i][0] >= 0 ) { //현재 무게에서 i번쨰 아이템의 무게 > 0 ( 즉, 본인 아이템을 담을 수 잇는지 확인 )
    				dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - arr[i][0] ] + arr[i][1]);
    			}
    		}
    	}
    	
    	System.out.println(dp[N][K]);
    	
    }
    
    
}

 

다르게 풀어본 코드입니다.

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 int N, M, C, K;
	public static Product[] product;
	public static int[][] dp;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		product = new Product[N];
		dp = new int[N + 1][100001];
		for(int i=0;i<=N;i++) {
			Arrays.fill(dp[i], -1);
		}
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			int inputW = Integer.parseInt(st.nextToken());
			int inputV = Integer.parseInt(st.nextToken());
			product[i] = new Product(inputW, inputV);
		}
		
		answer = simulate(0, K);
		System.out.println(answer);
	}
	public static int simulate(int level, int curK) {
		if(curK < 0) {
			return 0;
		}
		if(dp[level][curK] != -1) return dp[level][curK];
		if(level >= N) return 0;
		if(curK == 0) return 0;
		
		int resultA = 0, resultB = 0;
		if(curK - product[level].W >= 0) {
			resultA = product[level].V + simulate(level + 1, curK - product[level].W);	
		}
		resultB = simulate(level + 1, curK);
		 
		return dp[level][curK] = Math.max(resultA,  resultB);
	}
}

class Product{
	int W;
	int V;
	public Product(int W, int V) {
		this.W = W;
		this.V = V;
	}
	public Product() {
		
	}
}