背包问题
1. 01背包问题
有 N件物品和一个容量是 V的背包。每件物品只能使用一次。第i件物品的体积是\(v_i\),价值是\(w_i\)。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
/* f[i][j] 表示只看前i个物品，总体积是j的情况下，总价值最大是多少
f[i][j] = max(1.,2.):
1. 不选第i个物品，f[i][j] = f[i - 1][j];
2. 选第i个物品，f[i][j] = f[i - 1][j - v[i]];
*/
int n,m; // n为背包数量，m为总体积
int f[N][N];
int w[N],v[N];
for(int i = 1;i <= n;i ++ )
for(int j = 0;j <= m;j ++ )
{
f[i][j] = f[i - 1][j];
if(j >= v[i]) f[i][j] = max(f[i][j],f[i - 1][j - v[i]] + w[i]);
}
int res = 0;
for(int i = 0;i <= m;i ++ ) res = max(res,f[n][i]);
// 一维优化，由于f[i][j]计算中只用到了i-1的状态，因此可以将第一维优化掉
int f[N]; // f[j]表示体积为j时第i种物品的选择,i取决于外层循环
for(int i = 1;i <= n;i ++ )
for(int j = m;j >= v[i];j -- ) //从大到小枚举，保证计算f[j]时使用的f[j-v[i]]没有被使用过，即为f[i-1][j-v[i]]
f[j] = max(f[j],f[j - v[i]] + w[i]);
int res = f[m];
2. 完全背包问题
有 N种物品和一个容量是 V的背包，每种物品都有无限件可用。第i种物品的体积是\(v_i\),价值是\(w_i\)。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
// f[i] 表示总体积是i的情况下，最大价值是多少
for(int i = 1;i <= n;i ++ )
for(int j = v[i];j <= m;j ++ ) //与01背包对比，此处从小到大枚举j，即可保证计算f[j]的时候已经考虑了若干个第i个物品；
f[j] = max(f[j],f[j - v[i]] + w[i]);
int res = f[m];
// 若考虑体积恰好为m时的最大值，则将除f[0]以外的都初始化为负无穷，01背包同理
3. 多重背包问题
有 N种物品和一个容量是V的背包。第i种物品最多有\(s_i\)件，每件体积是\(v_i\)，价值是\(w_i\)。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
// f[i] 表示体积为i的情况下最大价值是多少
for(int i = 1;i <= n;i ++ )
for(int j = m;j >= 0;j --)
for(int k = 1;k <= s && k * v[i] <= j;k ++ )
f[j] = max(f[j],f[j - k * v[i]] + k * w[i]);
int res = f[m];
/*
优化1,适用于o(N*log(s)*V)复杂度，优化思路，将多重背包变成01背包问题
如果直接将s个物品拆成s份，时间复杂度仍然会很大，因此考虑二进制优化
s = 1 + 2 + 4 + ... + 2^k + s';其中k为最大的使2^k <= s的整数，这样使用logs个可以使用0或1次的物品即可凑出0到s所有的可能
*/
struct Good
{
int v,w;
};
vector<Good> goods;
for(int i = 0;i < n;i ++ )
{
for(int k = 1;k <= s;k *= 2)
{
s[i] -= k;
goods.push_back({v[i] * k,w[i] * k});
}
if(s > 0) goods.push_back({v[i] * s,w[i] * s});
}
for(auto good:goods)
for(int j = m;j >= good.v;j -- )
f[j] = max(f[j],f[j - good.v] + good.w);
int res = f[m];
4. 混合背包问题
有 N种物品和一个容量是 V的背包。
物品一共有三类：
第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 \(s_i\)次（多重背包）；
每种体积是 \(v_i\)，价值是 \(w_i\)。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
// 就是将三种以上三种背包问题混合起来，根据s的数值判断是使用哪种转移方程
int v[N],w[N],s[N];
int f[N];
int n,m;
int main(){
cin>>n>>m;
int v,w,s;
for(int i=1;i<=n;i++){
cin>>v>>w>>s;
if(!s)// s == 0 代表完全背包
for(int j=v;j<=m;j++)
f[j] = max(f[j],f[j-v]+w);
else{
if(s == -1) s = 1; // s = -1 代表01背包，将s置为1，转化为s=1的多重背包与其他多重背包一起进行二进制优化
for(int k=1;k<=s;k*=2){
for(int j=m;j>=v*k;j--)
f[j]=max(f[j],f[j-k*v]+k*w);
s-=k;
}
if(s)
for(int j=m;j>=s*v;j--)
f[j]=max(f[j],f[j-s*v]+w*s);
}
}
5. 二维费用的背包问题
有 N件物品和一个容量是V的背包，背包能承受的最大重量是 M。每件物品只能用一次。体积是 \(v_i\)，重量是\(m_i\)价值是\(w_i\)。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
/*
f[i][j] 体积为i重量为j的最大价值
01背包，体积和重量从大到小枚举
*/
for(int i = 1;i <= n;i ++ )
for(int j = V;j >= v[i];j -- )
for(int k = M;k >= m[i];k -- )
f[j][k] = max(f[j][k],f[j - v[i]][k - m[i]] + w[i]);
int res = f[V][M];
6. 分组背包问题
有N组物品和一个容量是V的背包。每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 \(v_{ij}\)，价值是\(w_{ij}\)，其中 i是组号，j是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
// f[j] 表示最大体积为j时的最大价值
// v[i][j]表示第i组第j个
for(int i = 0;i < n;i ++ )
for(int j = m;j >= 0;j -- )
for(int k = 0;k < s;k ++ )
if(j >= v[i][k]) f[j] = max(f[j],f[j - v[i][k]] + w[i][k]);
int res = f[m];
7. 有依赖的背包问题
有 N个物品和一个容量是 V的背包。物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。
如下图所示：
如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。
每件物品的编号是i，体积是\(v_i\)，价值是\(w_i\)，依赖的父节点编号是\(p_i\)。物品的下标范围是1…N。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
/*
f[i][j]表示以第i个节点为根节点的子树在体积为j的条件下的最大价值
将其考虑成分组背包问题，子节点对于每个可选的体积是一个组
*/
void dfs(int u)
{
for(int i = h[u];i != -1;i = ne[i])
{
int son = e[i];
dfs(son);
for(int j = m - v[u];j >= 0;j -- )
for(int k = 0;k <= j;k ++ )
f[u][j] = max(f[u][j],f[u][j - k] + f[son][k]);
}
for(int i = m;i >= v[u];i -- ) f[u][i] = f[u][i - v[u]] + w[u];
for(int i = 0;i < v[u];i ++ ) f[u][i] = 0;
}
dfs(root);
int res = f[root][m];
8. 背包问题求方案数
有N件物品和一个容量是 V的背包。每件物品只能使用一次。第i件物品的体积是\(v_i\)，价值是 \(w_i\)。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
求最优选法的方案数
/*
f[i] 体积为i的情况下的最大价值
g[i] 体积为i的情况下的方案数
*/
// 初始化
g[0] = 1;
for(int i = 1;i <= m;i ++ ) f[i] = -INF;
for(int i = 0;i < n;i ++ )
for(int j = m;j >= v[i];j -- )
{
int t = max(f[j],f[j - v[i]] + w[i]);
int s = 0;
if(t == f[j]) s += g[j];
if(t == f[j - v[i]] + w[i]) s += g[j - v];
f[j] = t,g[j] = s;
}
// 求解最优解
int maxw = 0;
for(int i = 0;i < n;i ++ ) maxw = max(maxw,f[i]);
int res = 0;
for(int i = 0;i <= m;i ++ )
if(maxw == f[i])
res += g[i]
9. 求背包问题的方案
有N件物品和一个容量是 V的背包。每件物品只能使用一次。第i件物品的体积是\(v_i\)，价值是\(w_i\)。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。
/*
f[i][j] 表示考虑前i个物品，最大体积为j的最大价值
*/
for(int i = n; i >= 1;i --)
for(int j = 0;j <= m;j ++ )
{
f[i][j] = f[i + 1][j];
if(j >= v[i]) f[i][j] = max(f[i][j],f[i + 1][j - v[i]] + w[i]);
}
int vol = m;
// 判断是从哪个方案转移过来
for(int i = 1;i <= n;i ++ )
if(f[i][vol] == f[i + 1][vol - v[i]] + w[i])
{
cout << i << ' ';
vol -= v[i];
}