ABOUT ME

Today
Yesterday
Total
  • 12865 평범한 배낭
    알고리즘/백준 2019. 3. 26. 15:07

    1. 문제



    2. 코드

    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
    26
    27
    28
    29
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
     
    using namespace std;
     
    int W[101];
    int V[101];
    int dp[101][100001];
     
    int main() {
        int N, K;
        scanf("%d %d"&N, &K);
        for (int i = 1; i <= N; i++)
            scanf("%d %d"&W[i], &V[i]);
     
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= K; j++) {
                if (W[i] <= j) {
                    int free_w = j - W[i];
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][free_w] + V[i]);
                }
                else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        printf("%d", dp[N][K]);
    }
    cs


    3. 후기

    dp배열은 다음과 같이 출력된다.


    0 0 0 0 0 13 13

    0 0 0 8 8 13 13

    0 0 6 8 8 13 14

    0 0 6 8 12 13 14


    w[i]와 v[i]의 i를 하나씩 늘려가면서 최댓값을 찾아낸다. 

    '알고리즘 > 백준' 카테고리의 다른 글

    5557 1학년  (0) 2019.03.27
    1495 기타리스트  (0) 2019.03.26
    11066 파일합치기  (0) 2019.03.25
    11058 크리보드  (0) 2019.03.21
    2294 동전 2  (0) 2019.03.19
Designed by Tistory.