二维费用背包
01背包进阶版
有N件物品和一个空间容量为C，重量容量为W的背包，第 i 件物品的空间费用为c[i] ，重量费用为 wi，价值是 vi，每种物品仅有一件，可以选择放或不放，求将哪些物品装入背包可使价值总和最大
01背包：
f[i][j]=max(f[i−1][j],f[i−1][j−w[i]]+v[i])
空间降维写法
for (int i = 1; i <= n; i++)
for (int j = V; j >= w[i]; j--)
f[j] = max(f[j], f[j - w[i]] + v[i])s;
二维费用
f[i][j][k]=max(f[i−1][j][k],f[i−1][j−c[i]][k-w[i]]+v[i])
根据经验我们就可以写出
for(int i=1; i<=n; i++)//枚举物品
for(int j=C; j>=c[i]; j--)//枚举两种状态
for(int k=W; k>=w[i]; k--)
f[j][k]=max(f[j][k],f[j-c[i]][k-w[i]]+v[i]);
其实就和从完全背包添加新的限制条件变形到多重背包一样，再01背包原来的状态中加一维以满足新的限制，就是二维费用背包，以此类推就不难应对二维费用完全背包，二位费用多重背包等组合拳
例题
洛谷 1507
让体积和承重有限的条件下多装载一些高卡路里的食物，每个食品只能使用一次
输入格式：
第一行 两个数 体积最大值(<400)和质量最大值(<400)
第二行 一个数 食品总数N(<50).
第三行－第3+N行
每行三个数 体积(<400) 质量(<400) 所含卡路里(<500)
输出格式：
一个数 所能达到的最大卡路里(int范围内)
#include<bits/stdc++.h>
using namespace std;
int V,M,n;
int v[100],w[100],e[100];//体积，质量，所含卡路里
int f[500][500];
int main()
{
scanf("%d%d%d",&V,&M,&n);
for(int i=1; i<=n; i++)
scanf("%d%d%d",&v[i],&w[i],&e[i]);
for(int i=1; i<=n; i++)//枚举物品
for(int j=V; j>=v[i]; j--)
for(int k=M; k>=w[i]; k--)//枚举两种状态
f[j][k]=max(f[j][k],f[j-v[i]][k-w[i]]+e[i]);
printf("%d",f[V][M]);
return 0;
}
HDU 2159
物品总个数的限制
费用的条件可能以这样的方式给出：最多只能取一共M件物品
其实就相当于多了一种件数的费用，每个物品的件数费用均为1，可以付出的最大件数费用为M
一维背包的种种思想方法，往往可以应用于二位背包问题的求解中
分组背包
有N件物品和一个容量为C的背包，第 i 件物品的空间费用为c[i] ，价值是 vi，这些物品被划分为若干组，每组中的物品互相冲突，最多选一件，求将哪些物品装入背包可使价值总和最大
问题转化为：是选择本组的一件，还是一件都不选？
前k组物品花费费用 j 能得到的最大价值：f [k] [j]
f[k][j]=max(f[k−1][j],f[k−1][j−c[i]]+v[i]∣物品i属于组k)
for (所有的组k)
for (int j = V; j >= 0; j--)
for (所有属于组k的i)
f[j] = max{f[j], f[j - c[i]] + v[i]}
例题
洛谷1757
#include <bits/stdc++.h>
using namespace std;
const int M=1010,N=1010;
int n,m;
int f[M],a[N],b[N],c[101][20],cc[101],cn;
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
{
int C;
scanf("%d%d%d",&a[i],&b[i],&C);
cn=max(cn,C);//cn记录共有几组
cc[C]++;//cc[]记录第C组共有几件物品
c[C][cc[C]]=i;//c[][]记录第C组第i件物品的的序号
}
for(int i=1;i<=cn;i++)//枚举cn个组
for(int j=m;j>=0;j--)//枚举容量
for(int k=1;k<=cc[i];k++)//枚举各组中物品的序号
if(j>=a[c[i][k]])
f[j]=max(f[j],f[j-a[c[i][k]]]+b[c[i][k]]);//套用状态转移方程
printf("%d
",f[m])；
}
HDU 1712
依赖背包
非树形（只有主件，附件）
物品间存在某种“依赖”的关系，若i1依赖于i2，表示若选物品i1(附件)，则必须选物品i2(主件)
主件和附件的概念，只有放了主件之后才能放与之相关联的附件
可以先对每种主件的 附件的集合 进行一次 01 背包处理，就可以先求出 对于每一种主件包括其附件的组合中，每种花费的最大价值
对于每一种主件的01背包处理：
for i：主件k的所有附件
for j：价值（0 ~ n-主件价值）
01背包递推
得到费用依次为0~C−w[i]所有这些值时相应的最大价值f′[0~C−w[i]]
那么这个主件及它的附件集合相当于V−c[i]+1 V-c[i]+1V−c[i]+1个物品的物品组，其中费用为c[i]+k c[i]+kc[i]+k的物品的价值为f′[k]+w[i] f'[k]+w[i]f
′/[k]+w[i]。也就是说原来指数级的策略中有很多策略都是冗余的，通过一次01背包后，将主件i ii转化为V−c[i]+1 V-c[i]+1V−c[i]+1个物品的物品组，就可以直接应用分组背包的算法解决问题了。
例题
洛谷 1064
HDU 3449
#include<cstdio>
#include<cstring>
int dp[60][100010];
int max(int a,int b){return a>b?a:b;}
int main()
{
int n,tot,i,j,k;
while(scanf("%d%d",&n,&tot)!=EOF)
{
int p,m,w,v;
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
{
scanf("%d%d",&p,&m);
for(j=0;j<p;j++)
dp[i][j]=-1;
for(j=p;j<=tot;j++)
dp[i][j]=dp[i-1][j-p];//继承上一层的结果,j-p是因为一定要买箱子
for(j=1;j<=m;j++)
{
scanf("%d%d",&w,&v);
for(k=tot;k>=w;k--)
{
if(dp[i][k-w]!=-1)
dp[i][k]=max(dp[i][k],dp[i][k-w]+v);//01背包部分
}
}
for(j=tot;j>=0;j--)//如果能更新上一层的状态，就更新。
dp[i][j]=max(dp[i][j],dp[i-1][j]);
}
printf("%d
",dp[n][tot]);
}
return 0;
}