poj1948（经典有关问题-二维背包 求面积最大三角形）

poj1948（经典问题-二维背包 求面积最大三角形）

题意：给n(n<=40)个木板，每个长度不超过40.问40条木板能够组成的最大三角形面积是多少。

解法：dp[i][j][k]表示前k个木板是否能够组成两个长度为i,j的组合，当然ij是相互没有重叠部分的。根据三角形的性质知道，i，j都不会大于等于周长的一半，所有取最大800就够了。滚动使用dp[i][j]可以将空间降到二维，为了避免i,j有重复使用同一个木板，从大向小反向dp。

代码：

/****************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>

using namespace std;

#define eps 1e-8
typedef long long LL;
int n;
int num[110];
bool dp[810][810];


double getarea(double a,double b,double c)
{
    double p=(a+b+c)/2.0;
    return sqrt(p*(p-a)*(p-b)*(p-c));
}
bool OK(int a,int b,int c)
{
    if(a+b<=c)
        return false;
    if(a+c<=b)
        return false;
    if(b+c<=a)
        return false;
    return true;
}
int main()
{
  scanf("%d",&n);
  int sum=0;
  for(int i=0;i<n;i++)
    scanf("%d",num+i),sum+=num[i];
    dp[0][0]=1;
  for(int i=0;i<n;i++)
  {
      for(int k=800;k>=0;k--)
      {
          for(int j=k;j>=0;j--)
          {
              if(k-num[i]>=0&&dp[k-num[i]][j])
                dp[k][j]=1;
              if(j-num[i]>=0&&dp[k][j-num[i]])
                dp[k][j]=1;
          }
      }
  }
  double ans=0;
  for(int i=0;i<=800;i++)
    for(int j=0;j<=i;j++)
  {
      if(dp[i][j]&&OK(i,j,sum-i-j))
        ans=max(ans,getarea(i,j,sum-i-j));
  }
  if(ans==0)
    cout<<"-1\n";
  else
  cout<<(int)(ans*1000)/10<<endl;
   return 0;
}