[Ch.10 - DP] 06. 최대점수 구하기 [+냅색 알고리즘]

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

 

설명

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.

각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다.

제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다.

(해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)

입력

첫 번째 줄에 문제의 개수N(1<=N<=50)과 제한 시간 M(10<=M<=300)이 주어집니다.

두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.

출력

첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.

예시 입력 1 

5 20
10 5
25 12
15 8
6 3
7 4

예시 출력 1

41

---

최대점수 구하기

: DFS와 DP로 풀이 가능하다.

 

문제의 개수가 많아지면, DP로 풀어야 한다.

 

문제 풀이 순서

1. 제한시간을 배열의 개수로 하는 배열 선언
2. 동전 교환 문제처럼 앞에서 부터 루프를 돌면, 중복 문제가 발생한다.
   • dy[j - pt]+ps
3. 뒤에서부터 루프를 돈다.
   • for(j = dy.length; j>=pt; j--) dy[j - pt] +ps;

 

---

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int[][] arr;
	static int[] dy;
	static int n,m;
	
	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();
		m=kb.nextInt();
		arr=new int[n][2];
		for(int i=0;i<n;i++) {
				arr[i][0]=kb.nextInt();
				arr[i][1]=kb.nextInt();
		}
		System.out.println(solution(arr));
		
	}
	static int solution(int[][] arr) {
		dy=new int[m+1];
		Arrays.fill(dy, 0);
		int answer=Integer.MIN_VALUE;
		for(int i=0;i<n;i++) {
			for(int j=m;j>=arr[i][1];j--) {
				dy[j]=Math.max(dy[j], dy[j-arr[i][1]]+arr[i][0]);
			}
		}
		//for(int x : dy) answer=Math.max(x, answer);
		//return answer;
		return dy[m];
	}

}

 

import java.util.*;
  
public class Main {
  static int[][] arr;
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int m = in.nextInt();
    arr= new int[n][2];
    for(int i=0;i<n;i++){
      for(int j=0;j<2;j++){
        arr[i][j]=in.nextInt();
      }
    }
    System.out.println(solution(n,m));
  }
  static int solution(int n, int m){
    int[] dy = new int[m+1];
    dy[0]=0;
    for(int i=0;i<n;i++){
      int ps=arr[i][0];
      int pt=arr[i][1];
      for(int j=m;j>=pt;j--){
        dy[j]=Math.max(dy[j], dy[j-pt]+ps);
      }
    }
    return dy[m];
  }
}

 

+) 세련된 풀이

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		int[] dy = new int[m + 1];
		for (int i = 0; i < n; i++) {
			int ps = kb.nextInt();
			int pt = kb.nextInt();
			for (int j = m; j >= pt; j--) {
				dy[j] = Math.max(dy[j], dy[j - pt] + ps);
			}
		}
		System.out.println(dy[m]);
	}

}

 

 

냅색 알고리즘 조건 : 기준 값을 길이로 하는 배열 생성, 기준에 따라 배열에 넣기 위한 변수 생성

(1) dy : 주어진 시간을 길이로 하는 배열로, dy[j] : 시간에 따라 받을 수 있는 최대 점수

(2) 문제 개수를 변수로 하는 반복문 -> 문제 풀 때마다, 걸리는 시간과 주어지는 점수 변수 생성

(3) pt : arr[i][1], ps : arr[i][0]을 이용해, 배열 dy를 반복문을 통해 채운다.

(4) 반복문의 변수 : 주어진 시간부터 시작해, 해당 문제를 풀 수 있는 시간보다 클 경우 반복

(5) dy[j]를 채우는데, 가능한 값은 기존 값과 (해당 문제를 풀지 않았을 때의 점수 + 해당 문제 푼 점수) 중 최댓값 선택

 

 

import java.util.Scanner;
  
public class Main {
  
//문제 풀이 순서
//제한시간을 배열의 개수로 하는 배열 선언
//동전 교환 문제처럼 앞에서 부터 루프를 돌면, 중복 문제가 발생한다.
//dy[j - pt]+ps
//뒤에서부터 루프를 돈다.
//for(j = dy.length; j>=pt; j--) dy[j - pt] +ps;

  static int[] dy;
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int m = in.nextInt();
    int[][] arr = new int[n][2];
    for(int i=0;i<n;i++){
      for(int j=0;j<2;j++){
        arr[i][j]=in.nextInt();
      }
    }
    System.out.println(solution(n,m,arr));
  }
  static int solution(int n, int m, int[][] arr){
    //dy[j] 배열은 j분에 얻을 수 있는 최대 점수
    dy=new int[m+1];
    //제한 시간을 길이로 하는 배열이므로, 최대 시간+1만큼의 길이
    //뒤에서 부터 루프를 돈다.
    
    //포인트 변수, 시간 변수
    //-> 문제 개수만큼 도는 반복문
    for(int i=0;i<n;i++){
      int ps = arr[i][0];
      int pt = arr[i][1];
      //문제 풀이 시간이 남아있을 경우 풀 수 있으므로, j: m부터, pt보다 크거나 같을 때 까지
//      for(int j=dy.length-1;j>=0;j--){
      for(int j=m; j>=pt;j--){
        //i번째 문제를 풀었을 때, j분에 얻을 수 있는 점수 : [j-pt]분에 얻을 수 있는 점수 + ps;
        dy[j]=Math.max(dy[j],dy[j-pt]+ps);
      }
    }
    return dy[m];
  }
}