背包问题

01背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

分析：由于刚入门dp,所以我们从头到尾尽可能分析得详细（不会一来就写出优化的解法）。

动态规划问题有两个关键，一是状态表示，二是状态转移

就这道题而言，有两个变量，分别是v和w,所以我们先开一个二维数组来表示状态，f[i][j]所表示的状态是一个集合，这个集合里面就包括了所有的选法，但是f[i][j]最后是一个数，这个数表示集合的某种属性，集合的属性通常有三种，最大、最小和数量，这里很明显我们的属性应该表示为最大值，那么这个集合包括哪些选法呢？

答案是在1-i个物品中选，然后总体积不超过j其实可以发现，就是把题目的最后要求的东西把常量换成变量就可以了（也就是相当于函数思想）。

这个确定了，就要考虑如何把这个状态和其他状态联系起来，其实就是给集合分类，分类的标准是不重、不漏。这里我们可以分确定不选第i个物品的，和一定选第i个物品的。这就把集合中的选择分成两份了，对于前者其实就是f[i-1][j]那对于后者就是f[i-1][j-vi]+w[i]那么最后写出状态转移方程，就是两个中取较大的

代码实现：

#include<iostream>
using namespace std;
const int N=1010;
int f[N][N];
int v[N],w[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    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]);
        }
    cout<<f[n][m];
}

优化：我们可以注意到f[i]只和f[i-1]有关，也就是说使用滚动数组来做，进而意味着我们可以降为一维

但是要注意，下面这种写法是错误的

for(int i=1;i<=n;i++)
    for(int j=v[i];j<=m;j++){//j可以直接从v[i]开始
        f[j]=max(f[j],f[j-v[i]]+w[i]]);
    }

在f[j]没有更新的时候，f[j]里面存的就是上一次更新的值，也就是所谓的f[i-1][j]但是f[j-v[i]]就不是i-1次更新的值了，而是第i次更新的值，原因是j是递增的，但是j-v[i]一定是小于j的，也就是说在第i次更新j的时候，j-v[i]在这一轮一定已经更新了，所以不符合状态转移方程

所以要倒序来遍历j，确保f[j-v[i]]是i-1下的状态

优化代码：

#include<iostream>
using namespace std;
const int N=1010;
int v[N],w[N],f[N];
int main()
{
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m];
}

完全背包问题

在之前的分析的基础上，我们来应用到完全背包问题

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

分析：状态的表示和01背包是一样的，状态转移也就是集合的划分不一样，我们之前是选和不选，这里我们就分成选0个，1个，2个……当然不可能是无限的，因为有限制

朴素做法:

#include<iostream>
using namespace std;
const int N=1010;
int f[N][N],v[N],w[N];
int main()
{
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k*v[i]<=j;k++)
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
    cout<<f[n][m];
}

进行优化，写出原始状态转移方程，然后找规律进行优化

优化后代码：

#include<iostream>
using namespace std;
const int N=1010;
int f[N][N],v[N],w[N];
int main()
{
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    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]>=0)f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
        }
    cout<<f[n][m];
}

再进一步优化，可以压缩到一维，就要用到01背包那个错误例子，也就是算的是i，也就是正序遍历就可以了。

#include<iostream>
using namespace std;
const int N=1010;
int f[N],v[N],w[N];
int main()
{
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
        for(int j=v[i];j<=m;j++){
            if(j-v[i]>=0)f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    cout<<f[m];
}

多重背包问题

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

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

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

首先按照之前的思路，暴力解法不难想

#include<iostream>
using namespace std;
const int N=110;
int v[N],s[N],w[N];
int f[N][N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
    cout<<f[n][m];
}

但是由于是三重循环，时间复杂度肯定是不能接受的，所以肯定得想办法优化。但是从状态转移方程的角度来看似乎是不能像完全背包问题那样优化的，所以得考虑其他方法。

这里介绍多重背包问题的经典优化方法，二进制优化法，比如要列举0-1023的所有情况，并不一定必须从0列举到1023，还可以直接分为1、2、4、8…512也就是将这些背包打包成1份 2份 … 512份，那么选这么一份就对应有一定的比例，这样就能凑出从0-1023的所有情况。这样就能从O(n)优化到O(logn)

那么如果剩下的怎么办呢？答案是直接打包成一份就好了，比如最后还剩下23个，那就把23个打包成一份

所谓打包成一份的意思，就是把他们看成一个整体，体积和价值都直接乘对应的比例。最后就拆分完之后，其实就把这个问题转化成了01背包问题

代码实现：

#include<iostream>
using namespace std;
const int N=25000,M=2010;
int v[N],w[N],f[N];//最后拆分后的也就是01背包的数组
int n,m;
int main()
{
    cin>>n>>m;
    int cnt=0;//用来记录拆分后还有多少个物品
    for(int i=1;i<=n;i++)
    {
        int a,b,s;
        cin>>a>>b>>s;
        int k=1;
        while(k<=s)
        {
            cnt++;
            v[cnt]=k*a;
            w[cnt]=k*b;
            s-=k;
            k*=2;
        }
        if(s>0)
        {
            cnt++;
            v[cnt]=s*a;
            w[cnt]=s*b;
        }
    }
    //拆分完之后就直接是01背包
    for(int i=1;i<=cnt;i++)
        for(int j=m;j>=v[i];j--)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m];
}

分组背包问题

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

分析：

还是跟之前一样的分析思路，差异点还是在状态转移上，每一组物品只能选一个，也就是每一个组从0到最多可选择的个数，这就是集合的划分，然后落实到代码上就可以了。

#include<iostream>
using namespace std;
const int N=110;
int f[N],w[N][N],v[N][N],s[N];
int main()
{
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        for(int j=0;j<s[i];j++)
        {
            cin>>v[i][j]>>w[i][j];
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
            for(int k=0;k<s[i];k++)
                if(j>=v[i][k])f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
    cout<<f[m];
}

注意，这里直接使用了一维优化。只需要记住，只要状态只与这一层和上一层有关就可以直接用一维，如果用上一层的结果就倒序遍历，用这一层的就正序遍历。