//0-1背包 Triangular  Pastures
//题目大意:给定一系列线段(长度可能相同可能不同),问能组成的最大三角形面积
//动态规划状态转移方程
//dp[i][j][k]==true表示前i根长度可以组成长度为j、k、sum-j-k,反之不可以
//题目链接http://poj.org/problem?id=1948
#include <stdio.h>
#include <string.h>
#include <math.h>

#define N 40
#define M 800

bool dp[M+1][M+1];
int sg[N+1];
int n,sum;

double area(int a,int b,int c){
    double p=(a+b+c)/2.0;
    return sqrt(p*(p-a)*(p-b)*(p-c));
}
/*
//三维实现:25948KB  313 ms
bool dp[N+1][M+1][M+1];
void solve(){
    double best=0.0;
    int i,j,k;
    memset(dp,false,sizeof(dp));
    dp[0][0][0]=true;
    for(i=1;i<=n;i++){
        for(j=0;j<=sum/2;j++){
            for(k=0;k<=sum/2;k++)
                dp[i][j][k]=dp[i-1][j][k] || j>=sg[i] && dp[i-1][j-sg[i]][k] || k>=sg[i] && dp[i-1][j][k-sg[i]];
        }
    }
    for(j=1;j<=sum/2;j++){
        for(k=1;k<=sum/2;k++)
            if(dp[n][j][k] && j+k>sum-j-k && sum-k>k && sum-j>j && area(j,k,sum-j-k)>best)
                best=area(j,k,sum-j-k);
    }
    if(fabs(best)<=10e-6)
        printf(“-1\n”);
    else
        printf(“%d\n”,(int)(best*100));
}
*/
//二维实现:812 KB  172 ms
void solve(){
    double best=0.0;
    int i,j,k;
    memset(dp,false,sizeof(dp));
    dp[0][0]=true;
    for(i=1;i<=n;i++){
        for(j=sum/2;j>=0;j–){
            for(k=sum/2;k>=0;k–)
                dp[j][k]=dp[j][k] || j>=sg[i] && dp[j-sg[i]][k] || k>=sg[i] && dp[j][k-sg[i]];
        }
    }
    for(j=1;j<=sum/2;j++){
        for(k=1;k<=sum/2;k++)
            if(dp[j][k] && j+k>sum-j-k && sum-k>k && sum-j>j && area(j,k,sum-j-k)>best)
                best=area(j,k,sum-j-k);
    }
    if(fabs(best)<=10e-6)
        printf(“-1\n”);
    else
        printf(“%d\n”,(int)(best*100));
}

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

One Thought on “背包九讲 第一讲 0-1背包2

  1. alice on 2012/07/28 at 02:04 said:

    从三维转换为二维。动态规划最重要的是状态方程,只是我没想出来,还是看了人家的状态方程后自己编的。

发表评论

电子邮件地址不会被公开。

Post Navigation