当前位置: 代码迷 >> 综合 >> 背包模板(多重背包联系)
  详细解决方案

背包模板(多重背包联系)

热度:19   发布时间:2024-01-15 07:58:55.0

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;
}

CodeForces - 106C Buns 多维背包

  相关解决方案