[Inflearn] 최대점수 구하기(DP, 냅색 알고리즘, knapsack algorithm)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

- 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어짐

- 제한시간 M 안에 N개의 문제 중 최대점수를 얻을 수 있도록 

- 해당 문제는 해당 시간이 걸리는 푸는 걸로 간주

- 한 유형당 한 개만 풀 수 있음

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

입력이 아래와 같이 주어지면,

5 20 (문제의 개수, 제한시간)

10 5

25 12

15 8

6 3

7 4

마찬가지로 dp[]는 제한시간의 한계라고 생각할 수 있다.

열은 i번째 문제까지 적용했을 경우,

행은 j시간 제한

dp를 2차원 배열로 만들어줘야하는 이유는 

문제 한 유형당 한 개만 풀 수 있다고 하였으므로, 문제를 한 개씩 비교해보기 위함이다.

먼저 0번째 문제를 적용했을 때, 0으로 초기화(당연히 문제를 하나도 안 풀었으므로)

//

다음으로 첫 번째 문제를 풀었을 경우,

점수 : 10, 시간 : 5

5분이 걸리므로 제한 시간 한계는 5부터 시작

1번째 문제를 한 번만 풀 수 있으므로 5분부터 20분까지는 10점의 점수를 얻게 된다.

여기서 dp[i][j] = max(dp[i][j], dp[i][j-time]+score)를 해주게되면, j가 10일 경우, 20을 저장하게 된다.

그러면 두 문제를 풀게되어버리므로 max(dp[i][j], dp[i-1][j-time]+score)로 이전 결과를 참조해주어야 한다.

//

다음으로 두 번째 문제까지 풀 경우,

점수 : 25, 시간 : 12

아래와 같은 결과를 볼 수 있다.

12분부터 20분까지 두 번째 문제를 적용해보아야 하는데,

i - 1 번째까지 풀어서 얻은 결과를 먼저 복사해주어야 한다. (12분부터 문제를 적용하게 되면, 0~11분까지는 0점으로 초기화되어있으므로)

i = 2, j(제한 시간 한계) = 12일 경우, dp[i-1][j-time] 즉, dp[1][0]을 참조하여 점수를 더해준다. 0 + 25

마찬가지로

i = 2, j = 13일 경우, dp[i-1][j-t] 즉, dp[1][1]을 참조하여 점수를 더해준다. 0 + 25

...

i = 2, j = 17일 경우, dp[i-1][j-t] 즉, dp[1][5]을 참조하여 점수를 더해준다. 10 + 25

...

//

다음으로 세 번째 문제까지 풀 경우,

점수 : 15, 시간 : 8

아래와 같은 결과를 볼 수 있다.

...

i = 3, j = 17,  dp[i-1][j-t] 즉, dp[2][9]을 참조하여 점수를 더해준다. 10 +15

i = 3, j = 18,  dp[i-1][j-t] 즉, dp[2][10]을 참조하여 점수를 더해준다. 10 +15

...

i = 3, j = 20,  dp[i-1][j-t] 즉, dp[2][12]을 참조하여 점수를 더해준다. 25 +15

//

위 동작대로 남은 dp[][]도 채워보면 아래 그림들처럼 될 수 있다.

i = 4,

i = 5,

결과는 dp[5][20], 즉, dp[N][M]이 된다.

그러나 !!!

위 과정은 입력값이 커질수록 메모리나 시간복잡도에서 굉장히 비효율적이다.

그래서 1차원 배열로도 이 문제를 해결할 수 있는 방법이 있다.

먼저 초기 배열 상태는 아래 그림과 같다.

1차원 배열에 이 문제를 적용하기 위해서는 문제가 중복되는 현상을 해결해야 한다.

정방향으로 적용하면 문제의 중복이 발생하지만, 역방향으로 적용하면 문제의 중복이 발생하지 않는다. 

첫 번째 문제로 10 5 가 입력되고,

i = 1일 때, idx 20부터 5까지 적용하면 문제가 중복되지 않고 1차원 배열로 해결할 수 있다.

다음, i = 2

i = 3

i = 4

i = 5

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

#include <cstdio> #include <vector> #include <algorithm> using namespace std;   int main(void) {     int N, M, i, j, s, t;     freopen("input.txt", "rt", stdin);     scanf("%d %d", &N, &M);    // 문제 개수, 제한시간     vector<vector<int> > dp(N+1, vector<int>(M+1));       for (i = 1; i <= N; i++) {         scanf("%d %d", &s, &t);    // 점수, 시간         dp[i] = dp[i - 1];           for (j = t; j <= M; j++) {             dp[i][j] = max(dp[i][j], dp[i - 1][j - t] + s);         }     }       printf("%d\n", dp[N][M]);       return 0; } Colored by Color Scripter

cs

line 15) 이전 결과를 복사

line 17~19) 제한 시간 한계를 작은 문제부터 구해나간다.

line 18) 풀이에서 설명한 것 처럼 점화식을 세운다.

ㅇ 최적화 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

#include <cstdio> #include <vector> #include <algorithm> using namespace std;   int main(void) {     int N, M, i, j, s, t;     freopen("input.txt", "rt", stdin);     scanf("%d %d", &N, &M);    // 문제 개수, 제한시간     vector<int> dp(M+1);       for (i = 1; i <= N; i++) {         scanf("%d %d", &s, &t);    // 점수, 시간           for (j = M; j >= t; j--)              dp[j] = max(dp[j], dp[j - t] + s);     }       printf("%d\n", dp[M]);       return 0; } Colored by Color Scripter

cs

#. Other code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

#include<bits/stdc++.h> using namespace std;   int main() {     ios::sync_with_stdio(false);     int n, m, ps, pt;     cin>>n>>m;     vector<int> dy(m+1);     for(int i=0; i<n; i++){         cin>>ps>>pt;         for(int j=m; j>=pt; j--){             dy[j]=max(dy[j], dy[j-pt]+ps);         }                 }     cout<<dy[m]<<"\n";             return 0; } Colored by Color Scripter

cs

#. Result

  - Input --------------------------------------------------------

5 20

10 5

25 12

15 8

6 3

7 4

------------------------------------------------------------------

  - Output --------------------------------------------------------

41

------------------------------------------------------------------