최대점수구하기(냅색)

 

 

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

class Main {

	static int m, n, answer;
	static int []dy;

	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);

		n = in.nextInt();		
		m = in.nextInt();
		int [] dy = new int[m+1];
		for (int i = 0 ; i< n; i++) {
			int ps =in.nextInt();
			int pt =in.nextInt();
			
			for ( int j=m; j >= pt; j-- ) {
				dy[j] = Math.max(dy[j], dy[j - pt]+ps);
			}
			
		}		
		System.out.println(dy[m]);
	}

}
ex)
input
5 20
10 5
25 12
15 8
6 3
7 4
output
41

 

 

최대점수표.xlsx

0.01MB