首页 > 其他 > 详细

POJ - 1948 二维01背包

时间:2018-01-14 14:08:45      阅读:67      评论:0      收藏:0      [点我收藏+]

标签:2.0   double   pos   c++   %d   ace   div   con   str   

T了两发,DP方程很简单粗暴
dp[i][j][k]:用前i物品使得容量分别为j和k的背包恰好装满
背包的调用只需一次即可,第一次T就是每次check都丧心病狂地背包一次
对于sum的枚举,其实i j枚举到sum/2就可以了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define scan(a) scanf("%d",&a)
#define rep(i,j,k) for(int i = j; i <= k; i++)
using namespace std;
const int maxn = 1666;

bool F[maxn][maxn];
int len[maxn],n;
double query(double a,double b,double c){
    double p=(a+b+c)/2.0;
    return sqrt(p*(p-a)*(p-b)*(p-c));
}
bool dp[2][maxn][maxn];
int C[maxn],W[maxn],V1,V2;
bool bag(int a,int b){
    V1=a,V2=b;
    rep(i,1,n){
        dp[i&1][0][0]=1;
        rep(j,0,V1){
            rep(k,0,V2){
                dp[i&1][j][k]|=dp[i-1&1][j][k];//not be used
                if(len[i]<=j) dp[i&1][j][k]|=dp[i-1&1][j-len[i]][k];
                if(len[i]<=k) dp[i&1][j][k]|=dp[i-1&1][j][k-len[i]];
            }
        }
    }
    return dp[n&1][V1][V2];
}

#define check(i,j) dp[n&1][i][j]
int main(){
    while(scan(n)!=EOF){
        int sum = 0;
        rep(i,1,n) scan(len[i]);
        rep(i,1,n) sum+=len[i];
        memset(F,0,sizeof F);
        double t=(double)sum/2;
        int tt=sum/2+1;
        int maxi=0,maxj=0;
        rep(i,1,tt){
            rep(j,1,tt){
                if(i+j>t){
                    F[i][j]=1;
                    maxi=i,maxj=j;
                }
                    
            }
        }
        double ans=0;
        bag(maxi,maxj); 
        rep(i,1,tt){
            rep(j,1,tt){
                int k = sum-i-j;
                if(F[i][j]&&k>=1&&i+j>k&&i+k>j&&j+k>i&&check(i,j)){
                    ans = max(ans,query(i,j,k));
                }
            }
        }
        long long aans= ans*100;
        printf("%lld\n",aans>0?aans:-1);
    }
    return 0;
}

POJ - 1948 二维01背包

标签:2.0   double   pos   c++   %d   ace   div   con   str   

原文:https://www.cnblogs.com/caturra/p/8283164.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号