최대점수 구하기 (냅색 알고리즘)

 

import java.util.Scanner;

public class Main06 {
	//냅색 알고리즘

	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		
		int n = kb.nextInt();
		int m = kb.nextInt();
		
		int[] dynamic = new int[m+1];
		
		for(int i=0; i<n; i++) {
			int score = kb.nextInt();
			int time = kb.nextInt();
			
			for(int j=m; j>=time; j--) {
				//앞에서부터 돌면 중복
				//뒤에서부터 돌아야 중복 회피
				dynamic[j] = Math.max(dynamic[j], dynamic[j-time]+score);
			}
		}
		
		System.out.println(dynamic[m]);
	}

}