背包问题基础(三种背包)

先声明一点:海哥天下第一!

然后贴上我的模板:
01背包 ZeroOnePack

#define maxn ?
int zp(int w[],int v[],int nkind,int maxweight)
{
int i,j;
int dp[maxn]={0};
//init 看情况初始化
for(i=0;i<nkind;i++)
for(j=maxweight;j>=w[i];j--)
if(dp[j]<dp[j-w[i]]+v[i])
                dp[j]=dp[j-w[i]]+v[i];
return dp[maxweight];
}

完全背包 CompletePack

#define maxn ?
int cp(int w[],int v[],int nkind,int maxweight)
{
int i,j;
int dp[maxn]={0};
//init 看情况初始化
for(i=0;i<nkind;i++)
for(j=w[i];j<=maxweight;j++)
if(dp[j]<dp[j-w[i]]+v[i])
                dp[j]=dp[j-w[i]]+v[i];
return dp[maxweight];
}

多重背包MultiplePack

//dp[weight]=value
#define maxn ?
int dp[maxn],nkind,maxweight;
void zp(int w,int v)
{
for(int j=maxweight;j>=w;j--)
if(dp[j]<dp[j-w]+v)
            dp[j]=dp[j-w]+v;
}
void cp(int w,int v)
{
for(int j=w;j<=maxweight;j++)
if(dp[j]<dp[j-w]+v)
            dp[j]=dp[j-w]+v;
}
void mp(int w[],int v[],int n[])
{
int i,j;
for(i=0;i<nkind;i++)
    {
if(n[i]*w[i]>=maxweight)
        {
            cp(w[i],v[i]);
continue;
        }
int k=1;
while(k<=n[i])
        {
            zp(k*w[i],k*v[i]);
            n[i]-=k;
            k*=2;
        }
        zp(n[i]*w[i],n[i]*v[i]);
    }
}

看情况用一用.多看看说不定就咯噔一下领悟了,再也不用看了