2022/05/16) 5. 최대점수 구하기(냅색 알고리즘) [Dynamic programming(동적계획법)]

1. 문제

<최대점수 구하기>
: N개의 문제를 풀려고 한다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어진다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야한다. (해당 문제는 해당시간이 걸리면 푸는 것으로 간주한다, 한 유형당 한 개만 풀 수있다.)
(첫 번째 줄에 문제의 개수N(1 <= N <= 20)과 제한 시간 M(10 <= M <= 300)이 주어진다. 두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어진다.)
제한 시간안에 얻을 수 있는 최대 점수를 출력한다.

2. 해결 방법

1. 한 유형당 한 개의 문제만 풀 수 있으므로, 이전에 풀었던 거스름돈문제와 다르게 중복적용이 돼선 안된다. 그리하여 뒤에서부터 푼다.
2. dy배열을 제한 시간만큼 생성하는데, dy의 인덱스번호(j)는 제한시간이 되고, dy[j]는 j시간동안 얻을 수 있는 최대점수가 된다.

3. 정답

        <script>
            function solution(m, arr){  
                //제한시간만큼의 배열을 생성한다,
                //기존값보다 크면 푼다.
                //중복적용조심! 그래서 뒤에서부터 돌기.
                let answer = 0;
                let dy = Array.from({length:m+1}, ()=>0);
                for(let i = 0; i < arr.length; i ++){ //문제개수까지
                    let ps = arr[i][0]; //problem score , problem time
                    let pt = arr[i][1];
                    for(let j = m; j >= pt; j --){
                        dy[j] = Math.max(dy[j], dy[j-pt]+ps); //풀기로했으니까 pt빼주고, 풀었으므로 ps 더해준다
                    }
                }
                answer = dy[m];
                return answer;
            }
            let arr=[[10, 5], [25, 12], [15, 8], [6, 3], [7, 4]];
            console.log(solution(20, arr));
        </script>

        <script>
            function solution(m, arr){  
                //제한시간만큼의 배열을 생성한다,
                //기존값보다 크면 푼다.
                //중복적용조심! 그래서 뒤에서부터 돌기.
                let answer = 0;
                let dy = Array.from({length:m+1}, ()=>0);
                for(let i = 0; i < arr.length; i ++){ //[10,5], [25, 12], [15, 8], [6, 3], [7, 4]
                    console.log(dy);
                    let ps = arr[i][0]; //ps = 10(점수) / 25
                    let pt = arr[i][1]; //pt = 5(시간) / 12
                    for(let j = m; j >= pt; j --){//dy배열 끝에서부터, 5까지. 20~5 time은 이 문제를 풀 수 있으니까!!! / 12까지. 
                        dy[j] = Math.max(dy[j], dy[j-pt]+ps); //풀기로했으니까 pt빼주고, 풀었으므로 ps 더해준다 / 
                    }//dy의 인덱스번호 : 시간, dy[j] : 점수
                }
                answer = dy[m];
                return answer;
            }
            let arr=[[10, 5], [25, 12], [15, 8], [6, 3], [7, 4]];
            console.log(solution(20, arr));
        </script>