0-1/完全背包/多重背包问题

0-1背包问题
dp[i][j]表示前i件物品，体积容量为j的背包所能获得的最大价值
决策是第i个物品选不选; 
转移方程 dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
n为物品数量，m为背包体积 
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++) 
if(j-v[i]>=0)dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);

可以发现我们的状态只由上一层前面的状态决定；
于是我们可以从后面枚举体积这样我们的状态转移还是正确的；
这样做是为了优化空间
for(int i=1;i<=n;i++)
for(int j=m;~j;j--)
if(j-v[i]>=0)f[j]=max(f[j],f[j-v[i]]+w[i]);

完全背包指的是每件物品可以无限装入背包；
决策是否使用第i件物品，如果使用我们的状态是由dp[i][j-v[i]]转移过来
因为物品i还有可能会被选； 
dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i]);

直接优化方程
//转移是从上一阶段的同v或者这阶段的
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
if(j-v[i]>=0)f[j]=max(f[j],f[j-v[i]]+w[i]); 

多重背包就是每件物品由次数限制；
这时候我们考虑二进制拆分；
二进制拆分有个性质是000001111它拆成1.2.4.8可以组成1-15的数
对于每一位我们可以那4个1我们可以选与不选一共16种组合
除去都不选的0000还有15种组合对应1-15，如1010表示拆分的8和2选进背包
用换元思想理解；
这样我们从最低位对一个数的二进制进行拆分直到当前位不能被拆而独立存在
如某物品数量为10；我们可以拆1 2 4发现8不能当作第四物品，所以第四件10-1-2-4=3独立存在
int v[100000],w[100000],p=0;
for(int i=1;i<=n;i++) 
{
    int t=1,s=a[i];
    while(s>=t)
    {
        v[++p]=t*v[i];
        w[p]=t*w[i];
        s-=t;
        t*=2;
    }
    if(s)//如果还有独立生成一件换元物品 
    {
        v[++p]=s*v[i];
        w[p]=s*w[i];
    }
}
//后续就是0-1背包数量为p,这里为了习惯我用n替换p；
for(int i=1;i<=n;i++)
for(int j=m;~j;j--)
if(j-v[i]>=0)f[j]=max(f[j],f[j-v[i]]+w[i]);

 单调队列优化多重背包（第一次写调了好久，跪了）

//V[i]为物品体积，w[i]为物品价值，c[i]为物品数量，
令b[i]=min(c[i],m/v[i]);//每件物品最多能取几件
dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
k∈[0,b[i]];
令mod=j%v[i],div=j/v[i];
j=div*v[i]+mod;
上式
j-k*v[i]=div*v[i]+mod-k*v[i];
div*v[i]+mod-k*v[i]=v[i]*(div-k)+mod;
换元令k1或者其他数为div-k;
div-k=k1
k1∈[div-b[i],div]一共b[i]+1个数，我们要维护的单调队列数为b[i]+1;
上式：v[i]*k1+mod+(div-k1)*w[i];
dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
变形
dp[i][j]=max(dp[i][j],dp[i-1][k1*v[i]+mod]+(div-k1)*w[i]);
整理一下：dp[i-1][k1*v[i]+mod]-k1*w[i]+div*w[i]; k1∈[div-b[i],j]
上面的转移方程
观察前面dp[i][j]到dp[i-1][k1*v[i]+mod]例如j+V[i]与j（modv[i]）同余那我们的方程是在原来转移上
加上mod mod+v[i] mod+2v[i]....j..j+v[i]这儿所有数（mod v[i]）同余所以我们只要维护b[i]+1长度的滑窗就能慢慢转移了；

复杂度是O（NV）每个状态都只会被算一次对于每个i都会通过mod从0 v[i] 2*v[i] --1 1+v[i] 1+2v[i]这样被填满到m；

题目ACWing 6多重背包3；

 1 #include
 2 using namespace std;
 3 const int N=1e3+5;
 4 const int M=2e4+5;
 5 int a[N],v[N],c[N],w[N],q[M],f[M],num[M];
 6 
 7 int main()
 8 {
 9   int n,m;
10   scanf("%d%d",&n,&m);
11   for(int i=1;i<=n;i++)
12   scanf("%d%d%d",&v[i],&w[i],&c[i]);
13   for(int i=1;i<=n;i++)
14   {
15     int k=min(c[i],m/v[i]);//k是上文的b[i]，这里应该要加1的；但是后面
16     for(int mod=0;mod)
17     {
18         int h=1,t=1;
19         for(int j=0;j*v[i]+mod<=m;j++)
20         {
21           int tmp=f[j*v[i]+mod]-j*w[i];      
22           while(h=q[t-1])t--;
23           q[t]=tmp;//这里我们维护的是数值和下标，后续我会贴出我只维护下标的错误地方；
24           num[t++]=j;
25           while(hk)h++;//这儿本来是j-num[h]+1，但是跟前面k+1被我消了，最原始都是加1的；
26           f[j*v[i]+mod]=max(f[j*v[i]+mod],q[h]+j*w[i]);//取max其实没必要，因为我们的更新顺序，一定是正确且唯一的这也是我们NV复杂度的原因；习惯了
27         }后面其实是q[h]+div*w[i]但是因为div=j/c[i]即 div=(j*v[i]+mod)/v[i]=j,其实因为mod是小于v[i]的
28     }
29   }
30   cout<endl;
31   
32   return 0;
33 }

 1 #include
 2 using namespace std;
 3 const int N=1e3+5;
 4 const int M=2e4+5;
 5 int a[N],v[N],c[N],w[N],q[M],f[M],num[M];
 6 
 7 int main()
 8 {
 9   int n,m;
10   scanf("%d%d",&n,&m);
11   for(int i=1;i<=n;i++)
12   scanf("%d%d%d",&v[i],&w[i],&c[i]);
13   for(int i=1;i<=n;i++)
14   {
15     int k=min(c[i],m/v[i]);
16     for(int mod=0;mod)
17     {
18         int h=1,t=1;
19         for(int j=0;j*v[i]+mod<=m;j++)这段代码是过不了的
20         {
21           int tmp=f[j*v[i]+mod]-j*w[i];这是我一开始想要通过维护下标同时维护最大值，调了蛮久才发现错误
22           while(h1]*v[i]+mod]-q[t-1]*w[i])<=tmp))t--;
23           q[t++]=j;
24           while(hk))h++;
25           f[j*v[i]+mod]=max(f[j*v[i]+mod],(f[q[h]*v[i]+mod]-q[h]*w[i]+j*w[i]));错误点在于我的f[q[h]*v[i]+mod]有可能被更新了用的是f[i]而不是f[i-1]的状态
26           
　　　　　　　　如果只存下标我们就不能滚动数组，要开二维数组f[i][j]
　　　　　　　 /*while(h=q[t-1])t--;
27           q[t]=tmp;
28           num[t++]=j;
29           while(hk)h++;
30           f[j*v[i]+mod]=max(f[j*v[i]+mod],q[h]+j*w[i]);*/
31         }
32     }
33   }
34   cout<endl;
35   
36   return 0;
37 }

 1 #include
 2 using namespace std;
 3 const int N=1e3+5;
 4 const int M=2e4+5;
 5 int a[N],v[N],c[N],w[N],q[M],f[N][M],num[M];
 6 
 7 int main()
 8 {
 9   int n,m;
10   scanf("%d%d",&n,&m);
11   for(int i=1;i<=n;i++)
12   scanf("%d%d%d",&v[i],&w[i],&c[i]);
13   for(int i=1;i<=n;i++)
14   {
15     int k=min(c[i],m/v[i]);
16     for(int mod=0;mod)
17     {
18         int h=0,t=0;
19         for(int j=0;j*v[i]+mod<=m;j++)
20         {
21           int tmp=f[i-1][j*v[i]+mod]-j*w[i];
22           while(h=(f[i-1][q[t-1]*v[i]+mod]-q[t-1]*w[i])))t--;
23           q[t++]=j;
24           while(hk)h++;
25           f[i][j*v[i]+mod]=max(f[i][j*v[i]+mod],f[i-1][q[h]*v[i]+mod]-q[h]*w[i]+j*w[i]);
26         }这样做废空间，当然要是开f[2][M]去滚动也行，所以第一种存数值和下标的是最合理的。完结撒花！
27     }
28   }
29   cout<endl;
30   
31   return 0;
32 }