背包专题练习-白红宇

背包专题练习

阅读量：4696 次

发布时间：2019-06-09

本文共 4264 字，大约阅读时间需要 14 分钟。

hdu1171多重背包

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int maxn=100005;const int INF=~0u>>1;int w[maxn],v[maxn],num[maxn],dp[500007];int main(){    int N;    while(~scanf("%d",&N)){        if(N<=0) break;        int sum=0;        for(int i=0;i
          
           V) for(int j=w[i];j<=V;++j) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);            else{                int t=1;                while(t
           
            =t*w[i];--j) dp[j]=max(dp[j],dp[j-t*w[i]]+t*v[i]); num[i]-=t; t<<=1; } for(int j=V;j>=num[i]*w[i];--j) dp[j]=max(dp[j],dp[j-num[i]*w[i]]+num[i]*v[i]); } } int A=-INF; for(int i=0;i<=V;++i) A=max(A,dp[i]); int B=sum-A; if(A

View Code

hdu1059二进制优化多重背包

#include 
      
       #include 
       
        using namespace std;const int maxn=10;const int INF=~0u>>1;int w[10],v[10],num[10],dp[120007];int main(){    for(int i=0;i<6;++i){        w[i]=i+1;v[i]=i+1;    }    int cas=0;    while(~scanf("%d",&num[0])){        int t=num[0];        for(int i=1;i<6;++i) scanf("%d",&num[i]),t+=num[i];        if(!t) break;t=0;        printf("Collection #%d:\n",++cas);        for(int i=0;i<6;++i) t+=num[i]*(i+1);        if(t&1) {            printf("Can't be divided.\n\n");continue;        }        for(int i=0;i<120007;++i) dp[i]=-INF;        dp[0]=0;        int mid=t/2,V=mid;        for(int i=0;i<6;++i){            if(num[i]*w[i]>V) for(int j=w[i];j<=V;++j) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);            else{                if(!num[i]) continue;                t=1;                while(t
        
         =t*w[i];--j) dp[j]=max(dp[j],dp[j-t*w[i]]+t*v[i]);                    num[i]-=t;                    t<<=1;                }                for(int j=V;j>=num[i]*w[i];--j) dp[j]=max(dp[j],dp[j-num[i]*w[i]]+num[i]*v[i]);            }        }        //如果能抽取mid容量，则剩下的物品一定是完好且独立的        if(dp[mid]>0){            printf("Can be divided.\n\n");        }        else{            printf("Can't be divided.\n\n");        }    }    return 0;}

View Code

hdu2546扣出一部分容量贪心

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int maxn=1005;const int INF=~0u>>1;int w[maxn],v[maxn],dp[maxn];int main(){    int N;    while(~scanf("%d",&N)){        if(!N) break;        for(int i=0;i
          
           =w[i];--j) dp[j]=min(dp[j],dp[j-w[i]]-v[i]);        }        int ans=INF;        for(int i=0;i<=m-5;++i) ans=min(ans,dp[i]);        printf("%d\n",ans+5-v[N-1]);    }    return 0;}

View Code

hdu1114完全背包

#include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn=505;const int INF=1e9;int w[maxn],v[maxn],dp[10005];int main(){    int a;++  a;    int T;scanf("%d",&T);    while(T--){        int E,F,N;scanf("%d%d",&E,&F);        int V=F-E;        scanf("%d",&N);        for(int i=0;i

View Code

hdu2191多重背包

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int maxn=105;int w[maxn],v[maxn],num[maxn],dp[maxn];int main(){    int T;scanf("%d",&T);    while(T--){        int n,m;scanf("%d%d",&n,&m);        int V=n;        for(int i=0;i
          
           V) for(int j=w[i];j<=V;++j) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);            else{                int t=1;                while(t
           
            =t*w[i];--j) dp[j]=max(dp[j],dp[j-t*w[i]]+t*v[i]); num[i]-=t; t<<=1; } for(int j=V;j>=num[i]*w[i];--j) dp[j]=max(dp[j],dp[j-num[i]*w[i]]+num[i]*v[i]); } } printf("%d\n",dp[V]); } return 0;}

View Code

hdu2602-01背包

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int maxn=1005;int w[maxn],v[maxn],dp[maxn];int main(){    int T;scanf("%d",&T);    while(T--){        int N,V;scanf("%d%d",&N,&V);        memset(dp,0,sizeof(dp));        for(int i=0;i
          
           =w[i];--j) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);        }        printf("%d\n",dp[V]);    }    return 0;}