poj 1948 Triangular Pastures(2D 0/1 백팩)

클릭하여 링크 열기 poj 1948
사고방식: 2차원 0/1 가방 분석: 1문제는 n개의 나무 막대기 중에서 m개를 골라 하나의 삼각형을 구성하도록 한다. 그래서 삼각형의 면적이 최대 2는 삼각형에 대해 두 변과 둘레를 알면 면적을 구할 수 있다. 0/1 가방의 사상에 따라 dp[i][j][k]는 앞의 i개의 나무 막대기가 첫 번째 변을 구성할 수 있는지 없는지는 길이 j이고 두 번째 길이는 k이다.만약 dp[j-v[i]][k] 또는 dp[j][k-v[i]가true라면 dp[j][k]는true3을 위해 우리가 가능한 모든 조합의 합을 구하고 모든 변의 길이를 열거한 다음에 가장 큰 면적 코드를 구한다.

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 45;
const int MAXN = 2010;
int n , sum , v[N];
bool dp[MAXN][MAXN];

int solve(){
    memset(dp , false , sizeof(dp));
    dp[0][0] = 1;
    for(int i = 1 ; i <= n ; i++){
        for(int j = sum/2 ; j >= 0 ; j--){  //             
            for(int k = j ; k >= 0 ; k--){//           ，     k <= j   
                if(j >= v[i] && dp[j-v[i]][k])
                    dp[j][k] = true;
                if(k >= v[i] && dp[j][k-v[i]])
                    dp[j][k] = true;
            }
        }
    }
    int ans;
    ans = -1;
    for(int j = 1 ; j <= sum/2 ; j++){
        for(int k = 1 ; k <= j ; k++){//      j >= k，  k   j
            int t = sum-j-k;
            if(dp[j][k] && t > 0 && j+k > t && j+t > k && t+k > j){
               //           ，   p  ， tmp       int
               double p=(t+j+k)/2.0;  
               int tmp=(int)(sqrt(p*(p-t)*(p-j)*(p-k))*100);
               ans = max(ans , tmp); 
            }
        } 
    }
    return ans;
}

int main(){
    while(scanf("%d" , &n) != EOF){
        sum = 0;
        for(int i = 1 ; i <= n ; i++){
           scanf("%d" , &v[i]); 
           sum += v[i];
        }
        printf("%d
" , solve()); 
    }
    return 0;
}