[ 자바스크립트(JavaScript) ] section10 - 5 - 최대 점수 구하기(냅색 알고리즘)

📍 section10 - 5 - 최대 점수 구하기(냅색 알고리즘)

문제: 선생님이 내주신 N 개의 문제를 풀려고 한다. 각 문제는 그것을 풀 때 얻는 점수와 푸는데 걸리는 시간이 주어진다. 제한시간 M 안에 N 개의 문제 중 최대 점수를 얻을 수 있도록 해야 한다. (해당 문제는 해당 시간이 걸리면 푸는 걸로 간주한다. 한 유형당 한 개만 풀 수 있다.) 첫 번째 줄에 문제의 개수 N과 제한 시간 M이 주어지고 두번째 줄부터 N줄에 걸쳐 문제를 풀 때 얻는 점수와 문제를 풀 때 걸리는 시간이 주어집니다.

 

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

// 출력
41

 

이전에 동일한 문제를 부분집합 + edgeCut으로 문제를 풀었다. 하지만, 만약에 문제의 개수가 100개 이상이거나 혹은 제한 시간이 많아질수록 재귀의 연산 횟수가 늘어나기 때문에 DFS로 풀 수 없다. 이럴 때는 DP 냅색 알고리즘으로 풀어야 한다. 또한, 냅색 알고리즘을 이용하기 위해 동전교환 문제처럼 앞에서부터 dp[j]를 비교하면 안 되는데 왜냐하면 동전 문제는 동전을 무한정 사용할 수 있지만 이 문제는 한 유형 당 문제 한 개만 풀 수 있기 때문이다. 그래서 앞에서부터 비교하는 방법보다는 뒤에서부터 비교하면 중복사용을 막을 수 있다.

 

1. dp[j]: j시간 안에 얻을 수 있는 최대 점수 (dp[15]: 15분 동안 얻을 수 있는 최대 점수)
2. 주어진 시간까지 dp를 0으로 초기화한다.(최대 값을 구해야 하기 때문에)
3. 문제 1개([10, 5])만 풀 때, 문제 2개까지 ([10, 5], [25, 12]) 풀 때 얻을 수 있는 최대 점수, 모든 문제까지 얻을 수 있는 최대 점수 이렇게 범위를 점차 넓혀가며 구한다.
4. 기존의 동전문제는 동전을 무한정 사용할 수 있어서 앞에서부터 구했는데, 이 문제는 중복 허용이 안되므로 뒤에서부터 푼다(j=m~pt)
5. 예를 들어, 첫 번째 문제([10, 5])와 두 번째 문제([25, 12])로 제한 시간내에 문제를 풀 때의 최대 점수를 구할 때 현재 ps=25, pt=12라고 한다면 m=20이므로 맨 처음은 20부터 시작한다. 20-12=8이고 (여기서 값을 빼주는 이유는 현재 문제를 풀 것이기 때문에 현재 문제를 풀기 이전의 최대 점수를 가져오기 위함이다.) 이때8분으로 얻었던 최대 점수는 10점이다. 여기에 지금 푸는 문제의 점수(ps=25)를 더한 값을 적용하면 dp[20]=35가 된다.
6. 최대 점수를 구하기 때문에서 기존 점수와 새로 푼 점수를 비교해서 더 큰 값을 dp에 넣자.(Math.max 이용)
7. 하단에 새로운 문제를 풀 때마다 최대 점수를 기록하고 있는 dp를 출력했다. 항상 새로운 문제를 풀 때마다 최대점 수로 갱신되는 것이 아니라는 것을 염두에 두자.

 

 

728x90

 

let n = 5;
let m = 20;
let arr = [[10, 5], [25, 12], [15, 8], [6, 3], [7, 4]];

console.log(solution(n, m, arr));

function solution(n, m, arr){
  let dp = Array.from({length: m+1}, ()=> 0);

  for (let i of arr){
    let ps = i[0];
    let pt = i[1];
    for (let j=m; j>=pt; j--){
      dp[j] = Math.max(dp[j], dp[j-pt]+ps);
    }
    console.log(dp)
  }
  return dp[m];
}

👉🏽
ps= 10 pt= 5 [
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 10, 10,
  10, 10, 10, 10, 10, 10, 10
]
ps= 25 pt= 12 [
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 25, 25,
  25, 25, 25, 35, 35, 35, 35
]
ps= 15 pt= 8 [
   0,  0,  0,  0,  0, 10, 10,
  10, 15, 15, 15, 15, 25, 25,
  25, 25, 25, 35, 35, 35, 40
]
ps= 6 pt= 3 [
   0,  0,  0,  6,  6, 10, 10,
  10, 16, 16, 16, 21, 25, 25,
  25, 31, 31, 35, 35, 35, 41
]
ps= 7 pt= 4 [
   0,  0,  0,  6,  7, 10, 10,
  13, 16, 17, 17, 21, 25, 25,
  25, 31, 32, 35, 35, 38, 41
]
41