[고급-8] 동적테이블 응용3

선물

n개의 선물을 한명씩 적절하게 분배.

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

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

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

W=a+b+c

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

a=W-(b+c)

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

#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)-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;
}