动态规划----背包总结

一:01背包

#include<cstdio>
#include<algorithm>  
using namespace std;  
int m,t;
int f[1001];
int w[1001],c[1001];
int main()
{
    scanf("%d %d",&t,&m);
    for(int i=1;i<=m;i++)
        scanf("%d %d",&w[i],&c[i]);
    for(int i=1;i<=m;i++)
        for(int j=t;j>=w[i];j--)
        {
            f[j]=max(f[j],f[j-w[i]]+c[i]);
        }
    printf("%d",f[t]);
}

01 背包

以上模板;

每个物体只有一个；

这里最基础的，以下是几题例题：

1.vijos 采药（noip）

2.vijos 装箱问题（noip）

二：完全背包

eg：1708: [Usaco2007 Oct]Money奶牛的硬币

#include<cstdio>
#include<cstring>
int map[30];
long long f[10010];
int main()
{
    int v,n;
    scanf("%d %d",&v,&n);
    for(int i=1;i<=v;i++) scanf("%d",&map[i]);
    f[0]=1;
    for(int i=1;i<=v;i++)
        for(int j=0;j<=n;j++)
            if(map[i]<=j&&f[j-map[i]]) f[j]+=f[j-map[i]];
    printf("%lld",f[n]);        
     
    return 0;
}

完全背包

以上模板;

每个物体有无限个；

以下是几题例题：

1.hdu 1248 寒冰王座完全背包

2.bzoj 1708: [Usaco2007 Oct]Money奶牛的硬币

三：多重背包

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::max;
const int N=217;
int v[N],w[N],m[N];
int dp[200010];
int main()
{
    int nv,n;
    scanf("%d %d",&n,&nv);
    for(int i=1;i<=n;i++)        
    {
        scanf("%d %d %d",&v[i],&w[i],&m[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(m[i]==1)
        {
            for(int j=nv;j>=v[i];j--)
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
        else if(m[i]>=1)
        {
            if(v[i]*m[i]>=nv)
            {
                for(int j=v[i];j<=nv;j++)
                    dp[j]=max(dp[j],dp[j-v[j]]+w[i]);
            }
            else 
            {
                int k=1;
                while(k<m[i])
                {
                    for(int j=nv;j>=v[i]*k;j--)
                        dp[j]=max(dp[j],dp[j-v[i]*k]+w[i]*k);
                    m[i]-=k;
                    k<<=1;
                }
                if(m[i]>0) 
                    for(int j=nv;j>=v[i]*m[i];j--)
                        dp[j]=max(dp[j],dp[j-v[i]*m[i]]+w[i]*m[i]);
            }
        }
        else 
        {
            for(int j=v[i];j<=nv;j++)
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    printf("%d",dp[nv]);
    return 0;
}

多重背包

以上模板;(我应该打成几个函数来处理 01 背包,完全背包)

每个物体有有限个；

codves 3269 混合背包

vijos 飞扬的小鸟

这是三种最基本的背包;

==================