背包问题(一维dp)

时间:2022-09-30 18:43:30

背包问题可谓是经典的动态规划问题,这里就给出01背包,完全背包,多重背包的核心内容吧。可以作为模板用哦背包问题(一维dp)

见代码:

<1>  01背包(w[i]代表重量,v[i]代表价值,V代表背包容量)

        for(int i=0;i<N;i++)
for(int j=V;j>=w[i];j--)
dp[j]=max(dp[j-w[i]]+v[i],dp[j]);

<2> 完全背包(完全背包跟01背包的代码很像)

         for(int i=0;i<N;i++)
for(int j=w[i];j<=V;j++)
dp[j]=max(dp[j-w[i]]+v[i],dp[j]);

<3> 多重背包

       说起多重背包,可以用单调队列优化,也可以用二进制优化,目前只学了二进制优化方法,以后补上单调队列算法优化。

      多重背包其实就是01背包与完全背包的结合题。(f[i].w代表重量,f[i].v代表价值,f[i].t代表数量,w代表背包容量)

      在二进制优化那边我的代码写的有点繁琐,可以更简洁,就交给你们啦。背包问题(一维dp)

        for(int i=0;i<=k;i++)
{
int sum=f[i].w*f[i].t;
if(sum>=w) //完全背包
{
for(int j=f[i].w;j<=w;j++)
dp[j]=max(dp[j],dp[j-f[i].w]+f[i].v);
}
else //二进制优化转化成01背包求解
{
int aa=1,cc=1,m,g;
while(cc<f[i].t)
{
m=aa*f[i].w;
g=aa*f[i].v;
aa*=2;
cc+=aa;
for(int j=w;j>=m;j--)
dp[j]=max(dp[j],dp[j-m]+g);
}
m=(f[i].t-(cc-aa))*f[i].w;
g=(f[i].t-(cc-aa))*f[i].v;
for(int j=w;j>=m;j--)
dp[j]=max(dp[j],dp[j-m]+g);
}
}