[Algorithm/Java] 알고리즘 자바 최대 점수 구하기 Knapsack (코딩테스트, Dynamic Programming, 동적 계획법, 냅색 알고리즘)

---

1. 문제 설명

• 설명
  이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.
  각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다.
  제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다.
  (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)
• 입력
  첫 번째 줄에 문제의 개수N(1<=N<=50)과 제한 시간 M(10<=M<=300)이 주어집니다.
  두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.
• 출력
  첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.

 

 

 

2. 문제 코드 및 풀이 설명

import java.util.Scanner;

public class MaximumScore {
  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.print(dy[m]);
  }
}

 

 

3. 출력 예시

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

출력
41

 

 

 

---

위의 내용은 인프런에서 수강할 수 있는 김태원님의 자바 알고리즘 문제풀이 강의를 바탕으로 공부한 내용을 정리한 내용입니다!

https://inf.run/iAi6

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의