문제

풀이

1. 물건들을 무게순으로 오름차순 정렬
2. dp 2차원 배열의 행은 물건 열은 무게
3. dp 배열의 값은 해당 무게에서 가치의 최댓값이다.
4. j-물건의 무게가 0 이상과 0 미만일 경우 구분해서 구해준다.

코드

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());
        Goods[] goods=new Goods[n];
        for(int i=0;i<n;i++){
            st=new StringTokenizer(br.readLine());
            int w=Integer.parseInt(st.nextToken());
            int v=Integer.parseInt(st.nextToken());
            goods[i]=new Goods(w,v);
        }
        Arrays.sort(goods);
        int[][] dp=new int[n+1][k+1];
        int ans=0;
        for(int i=1;i<n+1;i++){
            Goods item=goods[i-1];
            for(int j=1;j<k+1;j++){
                if(j-item.w>=0){
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-item.w]+item.v);
                }
                else dp[i][j]=dp[i-1][j];
                ans=Math.max(ans,dp[i][j]);
            }
        }

        System.out.println(ans);
    }

    static class Goods implements Comparable<Goods>{
        int w;
        int v;

        public Goods(int w, int v) {
            this.w = w;
            this.v = v;
        }

        @Override
        public int compareTo(Goods o) {
            return this.w-o.w;
        }
    }
}

#dp