分组背包问题

题目释义

给定若干组，每组中有若干个物品，每组中只能选择一个物品，要求在不超过背包容量的情况下找出价值之和最高的价值数

算法思想：

将每组物品中每个物品都用二维数组进行标记，在找物品的过程中使用01背包问题的类似方式，加上三重循环来依次遍历第i组中的每个物品

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

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

int main()
{
    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(v[i][k]<=j)  f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
            }
        }
    }

    cout<<f[m];

    return 0;
}

二进制优化多重背包问题

题目释义：

给定n个物品，每个物品都有价值，最多能使用s次，要求从这些物品中取出若干个物品，求在所有物品的体积之和不超过背包容量 j的情况下的最大价值之和；

算法思想：

在解决多重背包问题的过程中，如果使用暴力解法会大大加大运算量，导致超时报错，为了提高运算效率，我们使用二进制优化算法，对于每个物品，将原本要逐个遍历的算法变成用二进制表示的算法，随后转化成01背包问题进行求解（给定的1-s内的所有数都能被二进制的数表示出来）；

举个形象的例子：如果给定一个物品的最大使用次数的1000，我们根据二进制优化算法，会将其分成以下几组：

$1$ $2$ $4$ $8$ $16$ $32$ $64$ $128$ $256$ $489$($1000-(2^9-1))$

通过这些组来表示从1-1000中的所有的数，合理性何在呢？

首先我们可以知道每一个数都可以用二进制数表示数来，在给定的1-256这些组数中，可以表示所有的9位二进制数，只要一个数转化成二进制数之后是9位，都可以用这些数据组成的集合来表示，由于有这九个数，我们表示的范围首先在$1$-$511$($2^{10}$-1)
那么如何继续表示后面的数呢，别忘了我们还有489这个数，随后我们不能根据前面给定的9个数来表示512这个数，但是在表示512的过程中将489放进来，再用前面9个数来表示23就可以了
还看不懂点这篇题解

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 12010,M=2010;

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

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]=a*k;
            w[cnt]=b*k;
            s-=k;
            k*=2;
        }
        if(s>0){
        //每队一个物品的最多操作数进行操作，就使得cnt++
            cnt++;
            v[cnt]=s*a;
            w[cnt]=s*b;
        }
    }
    //在这里，所有的物品可以使用的次数，最终都转变成组数，完全转化为01背包问题
    n=cnt;

    //01背包问题的常规代码
    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];

    return 0;
}

二进制优化多重背包问题

题目释义：

给定n个物品，每个物品都有价值，最多能使用s次，要求从这些物品中取出若干个物品，求在所有物品的体积之和不超过背包容量 j的情况下的最大价值之和；

算法思想：

在解决多重背包问题的过程中，如果使用暴力解法会大大加大运算量，导致超时报错，为了提高运算效率，我们使用二进制优化算法，对于每个物品，将原本要逐个遍历的算法变成用二进制表示的算法，随后转化成01背包问题进行求解（给定的1-s内的所有数都能被二进制的数表示出来）；

举个形象的例子：如果给定一个物品的最大使用次数的1000，我们根据二进制优化算法，会将其分成以下几组：

$1$ $2$ $4$ $8$ $16$ $32$ $64$ $128$ $256$ $489$($1000-(2^9-1))$

通过这些组来表示从1-1000中的所有的数，合理性何在呢？

首先我们可以知道每一个数都可以用二进制数表示数来，在给定的1-256这些组数中，可以表示所有的9位二进制数，只要一个数转化成二进制数之后是9位，都可以用这些数据组成的集合来表示，由于有这九个数，我们表示的范围首先在$1$-$511$($2^{10}$-1)
那么如何继续表示后面的数呢，别忘了我们还有489这个数，随后我们不能根据前面给定的9个数来表示512这个数，但是在表示512的过程中将489放进来，再用前面9个数来表示23就可以了
还看不懂点这篇题解

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 12010,M=2010;

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

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]=a*k;
            w[cnt]=b*k;
            s-=k;
            k*=2;
        }
        if(s>0){
        //每队一个物品的最多操作数进行操作，就使得cnt++
            cnt++;
            v[cnt]=s*a;
            w[cnt]=s*b;
        }
    }
    //在这里，所有的物品可以使用的次数，最终都转变成组数，完全转化为01背包问题
    n=cnt;

    //01背包问题的常规代码
    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];

    return 0;
}

多重背包问题的暴力写法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n,m;
int s[N],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]>>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-v[i]*k]+w[i]*k);
            }
            // f[i][j]=f[i-1][j];
            // if(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
        }
    }

    cout<<f[n][m];

    return 0;
}

完全背包问题

题目释义：

给定一个n个物品和一个容量为m的背包，每个物品可以使用无穷多次，求背包中所装物品价值之和的最大值

算法思想：

f[i][j]表示从前i个物品中选择若干个体积之和不超过j的物品价值之和的最大值，对于第i个物品，根据有几个第i个物品来进行分类：
1. 对于没有第i个物品的情况，该情况可以转化为f[i-1][j];
2. 对于有第i个物品的情况，根据有多少个第i个物品再次分成若干类，假设第i个物品有k个，那么该情况就转换成f[i-1][j-v[i]*k]+k*w[i]；

但是在具体的实现过程中发现第二种情况可以化简，对于每一种f[i][j-v]，都可以使用f[i][j-v]+w来进行表示，因此代码如下：

二维代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    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][j-v[i]]+w[i]);
        }
    }

    cout<<f[n][m];

    return 0;
}

01背包问题和完全背包问题之间的异同点：

由状态转移方程可以清楚看到，两者之间的区别就在于完全背包问题在进行有第i个物品的讨论过程中，不需要引入第i-1层中的数据进行运算，换言之不需要使用逆序来进行运算

一维代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    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++){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }

    cout<<f[m];

    return 0;
}

完全背包问题

题目释义：

给定一个n个物品和一个容量为m的背包，每个物品可以使用无穷多次，求背包中所装物品价值之和的最大值

算法思想：

f[i][j]表示从前i个物品中选择若干个体积之和不超过j的物品价值之和的最大值，对于第i个物品，根据有几个第i个物品来进行分类：
1. 对于没有第i个物品的情况，该情况可以转化为f[i-1][j];
2. 对于有第i个物品的情况，根据有多少个第i个物品再次分成若干类，假设第i个物品有k个，那么该情况就转换成f[i-1][j-v[i]*k]+k*w[i]；

但是在具体的实现过程中发现第二种情况可以化简，对于每一种f[i][j-v]，都可以使用f[i][j-v]+w来进行表示，因此代码如下：

二维代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    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][j-v[i]]+w[i]);
        }
    }

    cout<<f[n][m];

    return 0;
}

01背包问题和完全背包问题之间的异同点：

由状态转移方程可以清楚看到，两者之间的区别就在于完全背包问题在进行有第i个物品的讨论过程中，不需要引入第i-1层中的数据进行运算，换言之不需要使用逆序来进行运算

一维代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    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++){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }

    cout<<f[m];

    return 0;
}

01背包问题

题目释义：

给定一个容量为m的背包，给定n个物品，每个物品只能最多只能使用一次，要求从n个物品中选出若干个物品，使得选出的所有物品中的容量之和不超过j并且价值最大；

算法思想：

从前i个物品中挑选总容量和不超过j来并存储价值的最大值分解成两种情况：
1. 不包含第i件物品：变成从前i-1个物品中寻找容量和不超过j来存储价值的最大值；
2，包含第i件物品：从前i-1个物品中来挑选容量和不超过j-v[i]来存储价值的最大值加上w[i](这里可以看作是首先将第i个物品放进来，在此基础上背包容量变小，同时最开始的就有初识价值w[i])。

二维背包问题代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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];

    //如果背包中一个物品也不放，那么最大值必然为0，该步骤已经被初始化，因此直接从放入一个武平开始
    for(int i=1;i<=n;i++)
        //背包总容量不断增加
        for(int j=1;j<=m;j++){
            //对于第一种情况，首先将从前i个物品中挑选总容量之和不超过j的情况化简为不包括第i个物品的情况
            //在这种情况下，不管三七二十一首先让f[i][j]等于之前挑选前i-1个物品，且容量之和不超过j的最大值
            f[i][j]=f[i-1][j];
            //对于第二种情况，首先要进行情况的判定，如果当前情况的容量小到连第i个物品都没有办法放进去就不放
            //第二种情况可以看作首先将第i个物品放入了背包，如果能放进去就继续执行之前思路中说的情况；
            if(j>=v[i])  f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
        }

    cout<<f[n][m]<<endl;

    return 0;
}

算法思想：

将二维的背包问题转化成一维的背包问题，核心的思想就是将各种步骤进行等价转化，之前的二维背包问题中f[i][j]表示从前i个物体中选择容量之和不大于j的物体总价值的最大值，这里一维的角度下将第一个维度去掉，只剩下第二个维度背包容量，这时的f[j]表示在之前进行的i轮当中体积之和不超过j的总价值之和；

在之前二维的背包问题的第二种情况（先假设将第i个物品放入背包）中，如果判断出背包容量无法放入第i个物品，直接跳过，这里直接在第二层循环中加入v[i]；

在原来的二维代码中，要更新第i层的容量为j的情况，要基于第i-1层的容量为j的判断，如果在一维代码中使用这种正序的实现方式，会将第i层容量为j的情况中原本第i-1层的数据使用第i层的数据进行替代，为了避免这种情况的发生，第二层循环使用逆序来进行更新，这样在使用第i-1层数据的时候就能够正常调用；

举个例子来说明：如果在判断体积为3的过程中，f[7]的值要求通过f[4]的值来进行更新，在二维的条件下，这里的f[4]本来应该是f[i-1][4]，但是在正序的条件下会首先将f[4]进行更新，f[4]在f[7]之前率先变成第i层的数据，与之前的转化不等价，因此要使用逆序来进行背包容量的遍历，这样在第i层进行f[7]的更新过程中，用到的f[4]还没有在第i层进行更新，还保留了第i-1层的f[4]值，因此只有逆序的转化是等价的；
解释思路的参考题解

一维背包问题代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    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];

    return 0;
}

01背包问题

题目释义：

给定一个容量为m的背包，给定n个物品，每个物品只能最多只能使用一次，要求从n个物品中选出若干个物品，使得选出的所有物品中的容量之和不超过j并且价值最大；

算法思想：

从前i个物品中挑选总容量和不超过j来并存储价值的最大值分解成两种情况：
1. 不包含第i件物品：变成从前i-1个物品中寻找容量和不超过j来存储价值的最大值；
2，包含第i件物品：从前i-1个物品中来挑选容量和不超过j-v[i]来存储价值的最大值加上w[i](这里可以看作是首先将第i个物品放进来，在此基础上背包容量变小，同时最开始的就有初识价值w[i])。

二维背包问题代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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];

    //如果背包中一个物品也不放，那么最大值必然为0，该步骤已经被初始化，因此直接从放入一个武平开始
    for(int i=1;i<=n;i++)
        //背包总容量不断增加
        for(int j=1;j<=m;j++){
            //对于第一种情况，首先将从前i个物品中挑选总容量之和不超过j的情况化简为不包括第i个物品的情况
            //在这种情况下，不管三七二十一首先让f[i][j]等于之前挑选前i-1个物品，且容量之和不超过j的最大值
            f[i][j]=f[i-1][j];
            //对于第二种情况，首先要进行情况的判定，如果当前情况的容量小到连第i个物品都没有办法放进去就不放
            //第二种情况可以看作首先将第i个物品放入了背包，如果能放进去就继续执行之前思路中说的情况；
            if(j>=v[i])  f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
        }

    cout<<f[n][m]<<endl;

    return 0;
}

算法思想：

将二维的背包问题转化成一维的背包问题，核心的思想就是将各种步骤进行等价转化，之前的二维背包问题中f[i][j]表示从前i个物体中选择容量之和不大于j的物体总价值的最大值，这里一维的角度下将第一个维度去掉，只剩下第二个维度背包容量，这时的f[j]表示在之前进行的i轮当中体积之和不超过j的总价值之和；

在之前二维的背包问题的第二种情况（先假设将第i个物品放入背包）中，如果判断出背包容量无法放入第i个物品，直接跳过，这里直接在第二层循环中加入v[i]；

在原来的二维代码中，要更新第i层的容量为j的情况，要基于第i-1层的容量为j的判断，如果在一维代码中使用这种正序的实现方式，会将第i层容量为j的情况中原本第i-1层的数据使用第i层的数据进行替代，为了避免这种情况的发生，第二层循环使用逆序来进行更新，这样在使用第i-1层数据的时候就能够正常调用；

举个例子来说明：如果在判断体积为3的过程中，f[7]的值要求通过f[4]的值来进行更新，在二维的条件下，这里的f[4]本来应该是f[i-1][4]，但是在正序的条件下会首先将f[4]进行更新，f[4]在f[7]之前率先变成第i层的数据，与之前的转化不等价，因此要使用逆序来进行背包容量的遍历，这样在第i层进行f[7]的更新过程中，用到的f[4]还没有在第i层进行更新，还保留了第i-1层的f[4]值，因此只有逆序的转化是等价的；
解释思路的参考题解

一维背包问题代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    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];

    return 0;
}

耍杂技的牛

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 5e4+10;
PII cow[N];

int main()
{
    int n;
    cin>>n;
    for (int i = 0; i < n; i ++ ){
        int w,s;
        cin>>w>>s;
        cow[i]={w+s,w};
    }

    sort(cow,cow+n);

    int sum=0,res=-2e9;

    for (int i = 0; i < n; i ++ ){
        int s=cow[i].first-cow[i].second,w=cow[i].second;

        res=max(res,sum-s);
        sum+=w;
    }

    cout<<res;

    return 0;
}