ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [고급-8] 동적테이블 응용3
    강의 2017. 1. 11. 10:14
    반응형
    선물
    n개의 선물을 한명씩 적절하게 분배.

    조건 1 : 각자의 부피는 [길동>=길순>=길삼]을 만족하도록분배한다.

    조건 2 : 다음의 d가 최소가 되도록 한다. d=(길동선물 부피의 합)-(길삼 선물의 부피 합)

    조건 3 : 같은 d가 되는 배분방법이 여럿일 경우에는 길동의 선물의 부피 합이 적은 방법을 선택한다.


    W=a+b+c

    1~k까지의 선물을 받았을 때, 길순이가 부피 b, 길삼이가 부피 c를 받을 상태는 존재하는가?


    a=W-(b+c)

    a값을 굳이 저장 안해도 구할 수 있다는 사실!


    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 <cstdio>
     
    int n, W, G[21], A, B, C, ans=987654321;
    bool DT[21][2001][2001];
    int main(){
        scanf("%d"&n);
        for(int i=1; i<=n; ++i){
            scanf("%d", G+1), W+=G[i];
        }
        DT[0][0][0= true;
        for(int i=1; i<=n; ++i){
            for(int a=0; a<=2000++a){
                for(int b=0; b<=2000++b){
                    DT[i][a][b] = (DT[i-1][a][b] ||
                        (a-G[i]<0?false : DT[i-1][a-G[i]][j]) ||
                        (b-G[i]<0?false : DT[i-1][a][b-G[i]]));
                }
            }
        }
        for(int a=0; a<=2000++a){
            for(int b=0; b<=2000++b)
                if(DT[n][a][b]){
                    if(W-(a+b) >= a && a >= b && W-(a+b)-<= ans)
                        ans = W-(a+b) - b, A=W-(a,b), B=a, C=b;
                }
        }
        printf("%d %d %d\n", A, B, C);
        return 0;
    }
    cs


    반응형

    '강의' 카테고리의 다른 글

    [고급-9] 동적테이블 응용4  (0) 2017.01.11
    [고급-7] 동적테이블 응용2  (0) 2017.01.09
    [고급-6] 동적 테이블의 응용1  (0) 2016.12.19
    [고급-5] 동적표와 상/하향식 설계  (0) 2016.12.19
    [고급-4] 재귀함수의 확장  (0) 2016.11.27

    댓글

Designed by Tistory.