01背包
void ZERO_ONE_PACK(int cost,int m,int w) //m一般为容量或限制条件
{for(int i=m;i>=cost;i--)//有的题方程是累加,比如计数方案数问题,注意初始化,一般dp[0]=1;dp[i]=max(dp[i], dp[i-cost]+w);
}
完全背包
//完全背包过程
void COMPLETE_PACK(int cost,int m,int w) //m一般为容量或限制条件
{for(int i=cost;i<=m;i++)//有的题方程是累加,比如计数方案数问题,注意初始化,一般dp[0]=1;dp[i]=max(dp[i],dp[i-cost]+w);
}
多重背包
//模板1
int dp[N];
void ZERO_ONE_PACK(int cost,int m,int w) //m一般为容量或限制条件
{for(int i=m;i>=cost;i--)//有的题方程是累加dp[i]=max(dp[i], dp[i-cost]+w);
}
//完全背包过程
void COMPLETE_PACK(int cost,int m,int w) //m一般为容量或限制条件
{for(int i=cost;i<=m;i++)//有的题方程是累加dp[i]=max(dp[i],dp[i-cost]+w);
}
void MULTIPLY_PACK(int cost,int m,int num,int w) //cost表示物品的花费,m一般为背包容量和限制条件,num表示该物品的数量,w表示物品的价值
{if(cost*num>=m){COMPLETE_PACK(cost,m,w);return ;}int k=1;while(k<num){ZERO_ONE_PACK(cost*k,m,k*w);num-=k;k*=2;}ZERO_ONE_PACK(cost*num,m,num*w);
}
int n,m,c0,d0;
int main()
{for(int i=1;i<=m;i++){MULTIPLY_PACK(c[i],n,num[i],d[i]);}cout<<dp[n]<<endl;return 0;
}
例题:POJ 2392 Space Elevator 贪心+多重背包
HDU 2844 Coins 多重背包
模板2
int dp[N];
void ZERO_ONE_PACK(int cost,int m,int w) //m一般为容量或限制条件
{for(int i=m;i>=cost;i--)//有的题方程是累加dp[i]=max(dp[i], dp[i-cost]+w);
}
//完全背包过程
void COMPLETE_PACK(int cost,int m,int w) //m一般为容量或限制条件
{for(int i=cost;i<=m;i++)//有的题方程是累加dp[i]=max(dp[i],dp[i-cost]+w);
}
void MULTIPLY_PACK(int cost,int m,int num,int w) //cost表示物品的花费,m一般为背包容量和限制条件,num表示该物品的数量,w表示物品的价值
{if(cost*num>=m){COMPLETE_PACK(cost,m,w);return ;}int k=1;while(k<num){ZERO_ONE_PACK(cost*k,m,k*w);num-=k;k*=2;}ZERO_ONE_PACK(cost*num,m,num*w);
}
int n,m,c0,d0;
int main()
{for(int i=1;i<=m;i++){MULTIPLY_PACK(c[i],n,num[i],d[i]);}cout<<dp[n]<<endl;return 0;
}