程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj1948（經典問題-二維背包求面積最大三角形）

poj1948（經典問題-二維背包求面積最大三角形）

編輯：C++入門知識

題意：給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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

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=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<