[백준] 12865번 : 평범한 배낭

문제

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

문제해결방법

이 문제를 해결하기 위해 DP[N+1][K+1] 배열을 사용했다.

먼저 n번째 꺼낸 물건의 무게와 가치를 w, v 이라고 했을 때, DP[n][k] 를 아래와 같이 채워주었다.

k가 w보다 작은 경우에는 DP[n-1][k] (꺼낸 물건과 관계없이 현재까지의 최대 가치가 변하지 않는다.),

k가 w이상인 경우에는 DP[n-1][k-w]+v 와 DP[n-1][k] 중에 더 큰 값

위 과정을 모두 반복하면 DP[N][K]를 통해 가방에 담을 수 있는 최대 가치를 구할 수 있다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main12865_평범한배낭 {
 
    public static void main(String[] args) throws Exception{
        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[][] DP = new int[N+1][K+1];
        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            for(int j=1; j<=K; j++) {
                if(j<w) DP[i][j] = DP[i-1][j];
                else DP[i][j] = Math.max(DP[i-1][j], DP[i-1][j-w]+v);
            }
        }
        System.out.println(DP[N][K]);
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.