多重背包模板题题解&学习笔记

1. 学习笔记

1.1 算法介绍

多重背包是告诉你有多少个物体重量以及价值，并且每种物品还外加了最多能取多少个。问你最大能凑出的价值。

1.2 算法流程

$$多重背包暴力做法$$

这个看过 完全背包 的同学应该不难想到，直接三重循环枚举空间和个数就好了。

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

const int N = 1010;

int dp[N][N];
int v[N],w[N],c[N];

int main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++) scanf("%d%d%d",&v[i],&w[i],&c[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)//枚举空间
        {
            for(int k=0;k<=c[i] && k*v[i]<=j;k++) dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+w[i]*k);//枚举当前要选几遍当前物品
        }
    }
    printf("%d",dp[n][m]);
}

$$多重背包二进制优化$$

大家记不记得小学奥数中有一道题？
小明有1~13克的砝码$13$个,请问最少要选其中多少个砝码才能称出1~13克中的所有重量？

这道小学奥数题不仅可以一个一个试，还可以用二进制。
我们只需要选$1$，$2$，$4$，$8$…这样一个一个选过去就好了
为什么？
首先，$1$可以凑出$1$
$1，2$可以凑数1~3
那么$1，2，4$就可以凑出1~7
因为为1~3可以凑出来了，$4$有单独了，所以可以。而5~7就相当于是凑出$4$加$1$或$2$或$1+2$。
接下来看$1，2，4，8$ 1~8可以凑出来了 凑出9~15分两种情况

凑出9~11 就相当于凑出$8$加上$1$和$2$的所有相加组合
凑出12~15相当于凑出$8$加$4$加$1$和$2$的所有相加组合

那么以此类推，每想凑出从当前数到下一项之间的所有数。就相当于当前项加上所有之前项的所有相加组合。
会不会感觉有点晕？看图：

我们只需要要将判断当前物品可选的次数拆解成$ 1* w[i] ,2 * w [i] ,4 * w[i]… $这样打包。再做一遍$01$背包就能得出答案了。因为根据上面的结论，二进制可以凑出 所有情况下的数，那么也自然可以凑出选了每个遍数的物体。

那么只要按照上述内容将一个物体按照能选的遍数二进制差分当成多个物体，然后做一遍$01$背包问题就迎刃而解了。（点个关注+赞吧我写到这起码花了一个小时）

2. 模板题题解

暴力枚举

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

const int N = 1010;

int dp[N][N];
int v[N],w[N],c[N];

int main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++) scanf("%d%d%d",&v[i],&w[i],&c[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)//枚举空间
        {
            for(int k=0;k<=c[i] && k*v[i]<=j;k++) dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+w[i]*k);//枚举当前要选几遍当前物品
        }
    }
    printf("%d",dp[n][m]);
}

二进制优化

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

const int N = 20010;
int dp[N];
int w[N],v[N];
int cnt=0;
int main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++)
    {
        int a,s,c;
        scanf("%d%d%d",&a,&s,&c);
        int k=1;
        while(k<=c)
        {
            cnt++;
            v[cnt]=a*k;//二进制差分，将v*k当成完整的一个物品使用
            w[cnt]=s*k;
            c-=k;
            k*=2;
        }
        if(c>0)//如果c减到剩下还有余话还得再打包，因为这说明二进制差分后还有余，不加上话c这个数凑不出来
        {
            cnt++;
            v[cnt]=a*c;
            w[cnt]=s*c;
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=m;j>=v[i];j--) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    }
    printf("%d",dp[m]);
}

写到这已经有气无力了，给个关注+赞吧，有什么说的不对的欢迎指出来！！

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

const int N = 20010;
int dp[N];
int w[N],v[N];
int cnt=0;
int main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++)
    {
        int a,s,c;
        scanf("%d%d%d",&a,&s,&c);
        int k=1;
        while(k<=c)
        {
            cnt++;
            v[cnt]=a*k;
            w[cnt]=s*k;
            c-=k;
            k*=2;
        }
        if(c>0)
        {
            cnt++;
            v[cnt]=a*c;
            w[cnt]=s*c;
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=m;j>=v[i];j--) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    }
    printf("%d",dp[m]);
}

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

const int N = 1010;

int dp[N][N];
int v[N],w[N],c[N];

int main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++) scanf("%d%d%d",&v[i],&w[i],&c[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=c[i] && k*v[i]<=j;k++) dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+w[i]*k);
        }
    }
    printf("%d",dp[n][m]);
}

完全背包模板题题解&学习笔记

1. 学习笔记

1.1 算法介绍

完全背包是用来算在一定空间中可以放$n$种物品，每种都可以用无限次。问最多能装多少价值。

1.2 算法流程

完全背包是直接使用一维来覆盖的。
记得我们上次说的 01背包一维优化 中的重复覆盖的问题吗？

之前我们是防止这种情况出现，所以将$j$的枚举方向变了。但是现在，由于每个物品可以重复选，我们就需要重复更新。所以我们就可以利用到01背包一维优化时的那种问题，将$j$从0~m枚举。

其他的因为都是要选择最大价值，所以状态转移方程一样。

所以我们就可以将01背包的代码copy过来修改了。

2.模板题题解

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

int n,m;
const int N = 1010;
int dp[N];
int v[N],w[N];
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)//将j的枚举方向变化
        {
            if(j>=v[i]) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//状态转移
        }
    }
    printf("%d",dp[m]);
}

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

int n,m;
const int N = 1010;
int dp[N];
int v[N],w[N];
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(j>=v[i]) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    printf("%d",dp[m]);
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
ll n,T;
ll d[N],b[N];
int main (){
    cin>>n>>T;
    ll ans=0;
    ll t=0;
    ll last=0;
    d[0]=0,b[0]=0;
    d[n+1]=T+1,b[n+1]=0;
    for (int i=0;i<=n+1;i++) {
        if (i>=1&&i<=n) scanf ("%lld %lld",&d[i],&b[i]);
        if (t>=d[i]-last){
            t-=d[i]-last;
            ans+=d[i]-last;
            t+=b[i];
        }
        else {
            ans+=min(t,T+1-last);
            t=b[i];
        }
        last=d[i];
    }
    cout<<ans;
    return 0;
}

01背包问题模板题题解&学习笔记

1 学习笔记

1.1 算法介绍

01背包问题是一种用来计算在一定的空间内能装下的价值最大为多少。有点类似小偷偷东西计算能拿走的最大价值是多少。

1.2 算法流程

$$二维01背包$$

我们可以用$dp_i$$_j$表示前$i$个物品使用$j$的空间所能装的最大价值。

然后考虑状态转移

$dp_i$$_-$$_1$$ _j$ 表示前$i-1$个物体使用$j$的空间可以装的最大价值。

考虑两种情况：

1. 不选择当前物品。那么直接就是使用$dp_i$$_-$$_1$$_j$,因为不选当前物体，就相当于前$i-1$个物品所能得到的最大价值,也就是$dp[i-1][j]$
2. 选择当前物品。因为我们要选择当前物品，所以我们需要给出这么多空间，所以第二维就是$j-v[i]$ ，由于前$i$个物品需要前$i-1$个物品推出来，所以第一维就是$i-1$,那么要通过前$i-1$个物品加上新选的物品的价值，就是$dp[i-1][j-v[i]]+w[i]$

我们需要将空间每个空间所能获得的最大值都求出来，以便推出新状态，所以结合上述内容，代码就是

for(int i=1;i<=n;i++)
{
    for(int j=0;j<=m;j++)//m表示背包容积
    {
        if(j>=v[i]/*v[i]表示第i个物体的体积*/) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]]);//更新，取最优解
    }
}

$$01背包一维优化$$

如果我们将代码的第一维省掉，代码会报错中的$dp[i]$就直接表示了前i个物品使用j空间所能保存的最大价值。这时更新状态可以直接覆盖，就相当于选新的物品更新了。

但是要注意，为了避免出现 bellman_ford算法 中连续更新直到终点导致无法准确判断是否用了$k$段(就是说，如果直接像刚才一样从$0 到 m$更新，我们更新了$k$的点,但是如果有一个点$j$需要使用点k更新，那么就直接更新了两遍)

如图：

但是如果$j$是从大到小枚举的话：

所以代码只需要去掉一维，然后改变$j$的枚举顺序就能得出答案。

2.模板题题解

二维01背包：

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

const int N = 1010;

int dp[N][N];
int c[N],d[N];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d",&c[i],&d[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(j-c[i]>=0)
            {
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+d[i]);
            }
            else dp[i][j]=dp[i-1][j];
        }
    }
    int mx=(int)-1e9;
    for(int i=0;i<=m;i++) mx=max(dp[n][i],mx);
    printf("%d",mx);
}

一维01背包

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1010;

int dp[1010];
int w[N],v[N];
signed main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=0;j--)
        {
            if(j>=v[i]) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    printf("%d",dp[m]);
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1010;

int dp[1010];
int w[N],v[N];
signed main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=0;j--)
        {
            if(j>=v[i]) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    printf("%d",dp[m]);
}

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

int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main()
{
    int __;
    scanf("%d", &__);
    while(__--)
    {
        int a,b,m;
        scanf("%d%d%d",&a,&b,&m);
        int x,y;
        int d=exgcd(a,m,x,y);
        if(b%d) puts("impossible");
        else
        {
            printf("%d\n",(long long)x*b/d%m);
        }
    }
}

其实就是floyd算法

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

const int N = 101;
int f[N][N];
int mp[N][N];
int main()
{
    int n;
    scanf("%d", &n);
    memset(f,0x3f3f3f,sizeof f);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int x;
            cin>>x;
            f[i][j]=x;
        }
    }

    int mx=0;
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
            }
        }
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mx=max(mx,f[i][j]);
    printf("%d",mx);
}