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

문제

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

풀이

• dp[i][j] = i개의 물건까지 고려했을 때 배낭 최대 허용 무게가 j인 경우 얻을 수 있는 최대 가치
• dp[i][j] = max(v + dp[i-1][j-w], dp[i-1][j])
• 현재 물건을 넣어주고 남은 무게를 채울 수 있는 최대값을 이전 물건 값에서 가져와 더해주거나,
• 현재 물건이 아닌 이전 물건으로 채우는 것 중에서 더 큰 값을 넣어줌

코드

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

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());
        List<Item> items = new ArrayList<>();
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            items.add(new Item(w, v));
        }
        int[][] dp = new int[N+1][K+1];
        Arrays.fill(dp[0], 0);
        for(int i=0; i<=N; i++){
            dp[i][0] = 0;
        }

        for(int i=1; i<=N; i++){
            for(int j=1; j<=K; j++){
                Item item = items.get(i-1);
                int w = item.w;
                int v = item.v;

                if(j<w){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(v+dp[i-1][j-w], dp[i-1][j]);
                }
            }
        }
        System.out.println(dp[N][K]);

    }
}

class Item{
    int w, v;
    Item(int w, int v){
        this.w = w;
        this.v = v;
    }
}