-
[고급-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값을 굳이 저장 안해도 구할 수 있다는 사실!
1234567891011121314151617181920212223242526272829#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;}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