头像

Stair

末2小趴菜




在线 


最近来访(82)
用户头像
雲流
用户头像
可乐_z
用户头像
Amaryllis_
用户头像
清清小苏打
用户头像
ash_heat
用户头像
lmwnl
用户头像
成狗
用户头像
T_13
用户头像
DKH
用户头像
胡想
用户头像
zedchou
用户头像
草驴
用户头像
PseudorandomGenerators
用户头像
TomCat
用户头像
L_H_R
用户头像
大聪明123
用户头像
Acwer
用户头像
瓜子鎏
用户头像
mirror_kiss
用户头像
anicaaovo

活动打卡代码 AcWing 9. 分组背包问题

Stair
15小时前

分组背包问题

题目释义

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

算法思想:

将每组物品中每个物品都用二维数组进行标记,在找物品的过程中使用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;
}



Stair
15小时前

二进制优化多重背包问题

题目释义:

给定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;
}


活动打卡代码 AcWing 5. 多重背包问题 II

Stair
15小时前

二进制优化多重背包问题

题目释义:

给定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;
}


活动打卡代码 AcWing 4. 多重背包问题

Stair
19小时前

多重背包问题的暴力写法

#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;
}



Stair
19小时前

完全背包问题

题目释义:

给定一个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]
屏幕截图 2023-02-04 141155.jpg
但是在具体的实现过程中发现第二种情况可以化简,对于每一种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背包问题和完全背包问题之间的异同点:

屏幕截图 2023-02-04 141405.jpg

由状态转移方程可以清楚看到,两者之间的区别就在于完全背包问题在进行有第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;
}


活动打卡代码 AcWing 3. 完全背包问题

Stair
19小时前

完全背包问题

题目释义:

给定一个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]
屏幕截图 2023-02-04 141155.jpg
但是在具体的实现过程中发现第二种情况可以化简,对于每一种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背包问题和完全背包问题之间的异同点:

屏幕截图 2023-02-04 141405.jpg

由状态转移方程可以清楚看到,两者之间的区别就在于完全背包问题在进行有第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;
}



Stair
20小时前

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


活动打卡代码 AcWing 2. 01背包问题

Stair
20小时前

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


新鲜事 原文

Stair
2天前
基础课就剩下DP了,明天休息一天,把之前学过的统一复习一下,然后和提高课一起开DP;


活动打卡代码 AcWing 125. 耍杂技的牛

Stair
2天前

耍杂技的牛

#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;
}