背包专题练习

hdu1171多重背包

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

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<N;++i){
            scanf("%d%d",&w[i],&num[i]);v[i]=w[i];sum+=num[i]*v[i];
        }
        int V=sum/2;
        for(int i=0;i<500007;++i) dp[i]=-INF;dp[0]=0;
        for(int i=0;i<N;++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{
                int t=1;
                while(t<num[i]){
                    for(int j=V;j>=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<B) swap(A,B);
        printf("%d %d
",A,B);
    }
    return 0;
}

hdu1059二进制优化多重背包

#include <iostream>
#include <cstdio>

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:
",++cas);
        for(int i=0;i<6;++i) t+=num[i]*(i+1);
        if(t&1) {
            printf("Can't be divided.

");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<num[i]){
                    for(int j=V;j>=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.

");
        }
        else{
            printf("Can't be divided.

");
        }
    }
    return 0;
}

hdu2546扣出一部分容量贪心

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
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<N;++i){
            scanf("%d",&w[i]);v[i]=w[i];
        }
        int m;scanf("%d",&m);
        sort(w,w+N);sort(v,v+N);
        if(m<5){
            printf("%d
",m);continue;
        }
        //买了x的最少剩余
        //把5和最贵的菜抠出来
        for(int i=0;i<maxn;++i) dp[i]=INF;dp[0]=m-5;
        for(int i=0;i<N-1;++i){
            for(int j=m-5;j>=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
",ans+5-v[N-1]);
    }
    return 0;
}

hdu1114完全背包

#include <iostream>
#include <cstdio>
#include <algorithm>
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<N;++i){
            scanf("%d%d",&v[i],&w[i]);
        }
        for(int i=0;i<=V;++i) dp[i]=INF;dp[0]=0;
        for(int i=0;i<N;++i){
            for(int j=w[i];j<=V;++j) dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
        }
        if(dp[V]==INF) printf("This is impossible.
");
        else{
            printf("The minimum amount of money in the piggy-bank is %d.
",dp[V]);
        }
    }
    return 0;
}

hdu2191多重背包

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
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<m;++i){
            scanf("%d%d%d",&w[i],&v[i],&num[i]);
        }
        memset(dp,0,sizeof(dp));
        for(int i=0;i<m;++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{
                int t=1;
                while(t<num[i]){
                    for(int j=V;j>=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
",dp[V]);
    }
    return 0;
}

hdu2602-01背包

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
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<N;++i){
            scanf("%d",&v[i]);
        }
        for(int i=0;i<N;++i){
            scanf("%d",&w[i]);
        }
        for(int i=0;i<N;++i){
            for(int j=V;j>=w[i];--j) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
        printf("%d
",dp[V]);
    }
    return 0;
}