背包九讲（改）

这个是我个人写的背包九讲，主要是基于我自己对于背包问题的讲解。

在此感谢知乎上的dd大牛的《背包九讲》和AcWing上的背包九讲总结（背包问题）

1.01背包问题

最为基础的背包问题。我们给定了一个有N件物品和一个容量为V的背包，第i件物品的费用为c[i]，价值为w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

思路的话，已经知道每种物品仅有一件，我们只能选择放和不放。所以我们可以用一个二维数组f[i][v]来维护我们的选择结果。此时我们能得到的状态转移方程为：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。

那我们下一步能不能优化一下呢？还真能。我们可以压成一维数组来优化我们的空间复杂度。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=1010;
int n,m,f[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,w;
        cin>>v>>w;
        for(int j=m;j>=v;j--)
        {
            f[j]=max(f[j],f[j-v]+w);
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

为什么能压成一维数组呢？仔细观察状态转移方程，如果我们能保证当第i次询问的时候我们实际上是在比较f[i-1][v]和f[i-1][v-c[i]]+w[i]，那么实际上我们完全可以省略第一维数组。于是我们在第二层循环中用V~0这样一个循环来保证我们的运算正确，因为这种遍历方式实际上在每次更新的时候用到的都是未被更新的数据。

2.完全背包问题

更为进阶的一种背包问题。有N种物品和一个容量是V的背包，每种物品都有无限件可用。第i种物品的体积是V_i，价值是W。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大，并输出最大价值。

与01背包问题的区别是，每种物品实际上有无限件可用。让我们回头去看在01背包问题那里给出的一维数组解决方案。还记得为什么我们要保证我们是V~0循环的吗？因为我们要保证每个物品只能用一次，而在这里，每个物品能用的次数却是无限的。所以只要我们把我们的循环从V~0转变为0~V，你就可以神奇的发现它就能非常完美地处理这一问题。

之所以我们可以这样做，关键在于实际上我们有了“加选第i件物品”的这样一个选择，所以如果这个物品空价比（空间比价值）足够高，我们就可以一直选择这一个物品，直到确实塞不下了再考虑其他的物品来填补剩下的空缺。

以下附带代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=1010;
int n,m,f[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,w;
        cin>>v>>w;
        for(int j=v;j<=m;j++)
        {
            f[j]=max(f[j],f[j-v]+w);
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

3.多重背包问题

（1）多重背包问题I

一个更为进阶的背包问题。有N种物品和一个容量是V的背包。第i种物品最多有S_i件，每件体积是V_i，价值是W_i。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大，并输出最大价值。

与01背包问题和完全背包问题都不同的地方是，在多重背包问题中，我们规定了每一个物品的数量为S_i，所以我们就不能简单的用V~0和0~V这种来解决问题了。

但是，我们可以通过把S_i件物品当作S_i个只有一件的物品来解决问题。这个就不详细说了，直接看代码即可理解。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=1010;
int n,m,f[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        for(int k=1;k<=s;k++)
        {
            for(int j=m;j>=v;j--)
            {
                f[j]=max(f[j],f[j-v]+w);
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

（2）多重背包问题II

题目描述与I一样，区别在于数据量大小的改变。自然我们就需要寻找一种更优的方案来解决问题。

首先先看代码。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

const int N=3010;
int n,m,f[N];
vector<int> ve;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        ve.clear();
        for(int p=1;p<s;p<<=1)
        {
            ve.push_back(p);
            s-=p;
        }
        if(s) ve.push_back(s);
        for(int k=0;k<ve.size();k++)
        {
            for(int j=m;j>=v*ve[k];j--)
            {
                f[j]=max(f[j],f[j-v*ve[k]]+w*ve[k]);
            }
        } 
    }
    cout<<f[m]<<endl;
    return 0;
}

我们可以利用二进制优化，将s件物品进行拆分，然后可以转化成01背包问题

（3）多重背包问题III

题目描述与I一样，区别在于数据量大小的改变，比II的数据量更大，此时我们就需要寻找一种更更优的方案来解决问题。

但是单调队列优化并非NOIP知识点，本人也没有学习练习，于是这里先跳过QWQ

4、混合背包问题

有N种物品和一个容量是V的背包。物品一共有三类：

• 第一类物品只能用1次（01背包）；
• 第二类物品可以用无限次（完全背包）；
• 第三类物品最多只能用S_i次（多重背包）；

每种体积是V_i，价值是W_i。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大，并输出最大价值。

没啥好说的，分类讨论（处理）。把前三种情况的模板代码合并起来就行了。

#include<bits/stdc++.h>
using namespace std;

int n,m,f[1010];
vector<int> ve;

int main()
{
    cin>>n>>m;
    while(n--)
    {
        int v,w,s;
        scanf("%d%d%d",&v,&w,&s);
        if(s==-1)
        {
            for(int j=m;j>=v;j--)
            {
                f[j]=max(f[j],f[j-v]+w);
            }
        }
        else if(s==0)
        {
            for(int j=v;j<=m;j++)
            {
                f[j]=max(f[j],f[j-v]+w);
            }
        }
        else
        {
            ve.clear();
            for(int p=1;p<s;p<<=1)
            {
                ve.push_back(p);
                s-=p;
            }
            if(s) ve.push_back(s);
            for(int k=0;k<ve.size();k++)
            {
                for(int j=m;j>=v*ve[k];j--)
                {
                    f[j]=max(f[j],f[j-v*ve[k]]+w*ve[k]);
                }
            }
        }
    }
    cout<<f[m];
    return 0;
}

5. 二维费用背包问题

有N件物品和一个容量是V的背包，背包能承受的最大重量是M。每件物品只能用一次。体积是 v_i，重量是m_i，价值是w_i。求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大，并输出最大价值。

简单来说，就是又加了一层限制。我们可以去用for(int j=M;j>=m;j--)来判断我们的操作是否在范围允许之内。

#include<bits/stdc++.h>
using namespace std;

int n,V,M,f[1010][1010];

int main()
{
    cin>>n>>V>>M;
    while(n--)
    {
        int v,m,w;
        cin>>v>>m>>w;
        for(int i=V;i>=v;i--)
            for(int j=M;j>=m;j--)
                f[i][j]=max(f[i][j],f[i-v][j-m]+w);
    }
    cout<<f[V][M]<<endl;
    return 0;
}

6. 分组背包问题

有N组物品和一个容量是V的背包。每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是v_ij，价值是w_ij，其中i是组号，j是组内编号。求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大，并输出最大价值。

为了方便解说，我在此先附上代码：

#include<bits/stdc++.h>
using namespace std;

const int N=110;
int n,m,f[N],v[N],w[N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int s;
        cin>>s;
        for(int j=1;j<=s;j++) cin>>v[j]>>w[j];
        for(int j=m;j>=0;j--)
        {
            for(int t=1;t<=s;t++)
            {
                if(j>=v[t])
                f[j]=max(f[j],f[j-v[t]]+w[t]);
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;

一个显著的地方在于for(int j=m;j>=0;j--)和for(int t=1;t<=s;t++)这两个循环。我们依靠这两个循环，即“在同一组内选择一个最优的物品”来满足题目所给的要求。

7.背包问题求方案数

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出 最优选法的方案数。注意答案可能很大，请输出答案模 109+7 的结果。

还是与上面一样先附带代码。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N=1010,mod=1e9+7;
int n,m,f[N],cnt[N];

int main()
{
    cin>>n>>m;
    for(int i=0;i<=m;i++) cnt[i]=1;
    for(int i=1;i<=n;i++)
    {
        int v,w;
        cin>>v>>w;
        for(int j=m;j>=v;j--)
        {
            int val=f[j-v]+w;
            if(val>f[j])
            {
                f[j]=val;
                cnt[j]=cnt[j-v];
            }
            else if(val==f[j]) cnt[j]=(cnt[j]+cnt[j-v])%mod;
        }
    }
    cout<<cnt[m];
    return 0;
}

这里的 f( i , j ) 实际上是发生了改变的，现在它表示只从前 i 个物品中选，体积恰好是 j 的最大价值。为了记录我们的结果，我们需要一个 cnt( i , j ) 来记录 f( i , j ) 取最大值的时候我们的方案数。

考虑到本题实际上是01背包问题的结合，于是我们依旧可以把二维数组压缩成一个一维数组。据此我们也可以把 cnt( i , j ) 也优化成一维数组。

8.背包问题求具体方案

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

还是像前面一样先附带代码。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

const int N=1005;

int n, m;
int v[N],w[N];
int f[N][N];

int main()
{

    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    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 j=m;
    for(int i=1;i<=n;i++)
        if (j>=v[i]&&f[i][j]==f[i+1][j-v[i]]+w[i])
        {
            cout<<i<<' ';
            j-=v[i];
        }
    return 0;
}

对于每个物品 i ，无非三种情况：第一种是必须选 i ，第二种是一定不会选择 i ，第三种是可以选择 i 也可以不选择。根据这三种情况更新 f ( i , j ) 即可。

对于该题目这种情况，我们还需要对代码做出一定的改进。题目要求输出字典序最小的方案，因此我们应该反过来遍历物品（从物品n开始遍历到物品1），求出数组 f 后，之后就可以从物品1开始考察，能选则选，然后考虑物品2，……，这样得到的结果字典序最小。

9.有依赖的背包问题

有 N 个物品和一个容量是 V 的背包。物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。如下图所示：

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。每件物品的编号是 i ，体积是 v_i ，价值是 w_i ，依赖的父节点编号是 p_i。物品的下标范围是 1…N。求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。输出最大价值。

树形DP的模板题目。先附上代码。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=110;
int n,m,r,f[N][N],v[N],w[N];
vector<int> g[N];

void dfs(int x)
{
	for(int i=v[x];i<=m;i++) 
		f[x][i]=w[x];	
	for(int i=0;i<g[x].size();i++)
	{
	    int y=g[x][i];
	    dfs(y);
	    for(int j=m;j>=v[x];j--)
		    for(int k=0;k<=j-v[x];k++)
			    f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]);
	}
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int fa;
		cin>>v[i]>>w[i]>>fa;
		if(fa==-1) r=i;
		else g[fa].push_back(i);
	}
	dfs(r);
	cout<<f[r][m];
	return 0;
}

在此，我们先使用邻接表来存储我们的树。这里使用的是数组模拟邻接表。我们在这里用 f[ x ][ j ] 来表示在以 x 为根的子树中选且总体积不超过 j 的方案。题目要求我们总价值最大，于是依旧采用max（毕竟也不可能让你找min是吧OWO）。然后这个问题也就解决了。

完结！这篇文章也许到后面还是会不断优化，但是现在先写到这里吧。