二维费用背包

问题描述

简单地说，就是 限制条件有两个 的情况

方法

再多开一维即可

二维 0-1 背包

先上例题：「Luogu P1855」榨取 kkksc03

状态转移方程

f[i][j][k]=max(f[i-1][j][k],f[i-1][j-v[i]][k-w[i]]+c[i])

同样使用滚动数组优化掉一维，压缩至二维，得到：

f[j][k]=max(f[j][k],f[j-v[i]][k-w[i]]+c[i])

考虑枚举顺序，要保证 f[j][k] 先于 f[j-v[i][k-w[i]] 更新，故应逆序枚举 j、k

代码如下：

for(int j=V;j>=0;j--)
    for(int k=W;k>=0;k--)
        f[j][k]=max(f[j][k],f[j-v[i]][k-w[i]]+c[i]);

二维完全背包

上例题：没找到 qwq

0-1 背包枚举顺序改一下就好了，代码如下：

for(int j=0;j<=V;j++)
    for(int k=0;k<=W;k++)
        f[j][k]=max(f[j][k],f[j-v[i]][k-w[i]]+c[i]);

二维多重背包

上例题：也没找到 qwq

总之很简单拉

评论