前言

今天跟着背包九讲把背包再学习一下，dd_engi大佬的背包九讲Github链接: 背包九讲

1. 采药(01背包)

题意

有 $n$ 个价值为 $w_i$ ，体积为 $v_i$ 的物品，装入体积为 $V$ 的背包中，问能获得的最大为多少。

思路

首先我们可以用 $f[i][j]$ 来定义前 $i$ 个物品放入体积为 $j$ 的背包中能获得最大体积，对于每一个物品，我们可以分两种情况来讨论，分别是装和不装，然后取他们两个的最大值。已经正确的定义了状态，转移方程就不难写出来了，是 $f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])$ ，然后推的话就直接外层循环物品，内层循环体积递推即可。最后 $f[n][V]$ 就是我们需要的答案。

但是看了大佬们的题解，他们说，空间复杂度还可以再优化，那么我们可以看看如果优化的话，肯定是不能去掉体积那一维的，所以就是去掉第几个物品那一维。所以从 $f[i][j]$ 变成了 $f[j]$ 。那么我们想想，当我们推第 $i$ 个物体的状态的时候，我们需要已知第 $i-1$ 个的状态，我们物体循环是 $1\sim n$ 那么肯定 $f[i][j]$ 一开始对应的是 $f[i-1][j]$ ，那么如果顺推体积 $0\sim V$ 的话我们可以发现，当我们推 $f[i][j]$ 需要状态 $f[i-1][j-v[i]]$ 的时候，这时候如果直接调用 $f[j-v[i]]$ 对应的是 $f[i][j-v[i]]$ 也就是说，这不是我们需要的结果，这时候的状态可能已经取过一次i了，那么我们就可以逆推体积 $V\sim c[i]$ ，这样我们调用 $f[j-v[i]]$ 就刚好对应的是没取过 $i$ 的情况了！最后推出来 $f[V]$ 就是对应的答案了！

代码实现

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>

using namespace std;

const int maxn=105;
int t,m;
int f[1005];
int a[maxn],b[maxn];
int main()
{
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=t;j>=a[i];j--)
        {
            f[j]=max(f[j],f[j-a[i]]+b[i]);
        }
    }
    printf("%d",f[t]);
    return 0;
}

2. 疯狂的采药(完全背包)

题意

有 $n$ 种价值为 $w_i$ ，体积为 $v_i$ 的物品，每一种物品有无数个，装入体积为 $V$ 的背包中，问能获得的最大为多少。

思路

那么很显然我们可以把一个它转化成 $\sum_{i=1}^n \lfloor{\frac{V}{v_i}}\rfloor$ 个物品的01背包，也可以在取每个物体的时候循环 $\lfloor{\frac{V}{v_i}}\rfloor$ 次，但是我们可以思考对上述01背包的优化，我们发现如果顺着取，刚好对应的就是我们需要的状态，也就是说我们只需要将 $V$ 的循环正过来就可以了！

代码实现

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>

using namespace std;

const int maxn=100005;
int t,m;
int f[100005];
int a[maxn],b[maxn];
int main()
{
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=a[i];j<=t;j++)
        {
            f[j]=max(f[j],f[j-a[i]]+b[i]);
        }
    }
    printf("%d",f[t]);
    return 0;
}

3. 宝物筛选(多重背包)

题意

有 $N$ 种物品和一个容量为 $V$ 的背包。第 $i$ 种物品最多有 $m_i$ 件可用，每件耗费的空间是 $v_i$，价值是 $w_i$ 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

思路

那么这道题裸的做法就是对于转移 $f[v]$ 这个方程的时候，考虑取多少个物品，可以取一个，可以取两个，在不超过体积情况下最多取 $m[i]$ 个，转移方程 $f[v]=max(f[v],f[v-k*v[i]])\quad k\in[1,m_i]$ 。那么这样其实时间复杂度还是很高的，所以大佬们给出了优化方案

  • 第一种就是把 $m_i$ 个物品进行二进制拆分，把他们拆成 $1$，$2^1$，$2^2$ ····等等，一直拆到不能再拆，这样我们就能够将 $m_i$ 个物品拆成 $log(m_i)$ 个物品，但是他们还是能够表示出所有的情况。然后就继续01背包背一下就可以了。
  • 单调队列优化，我不会，我太菜了。。

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,ans,cnt;
int a,b,c;
const int maxn=1000005;
int f[maxn];
int w[maxn],v[maxn];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        for(int j=1;j<=c;j*=2) //二进制拆分
        {
            v[++cnt]=j*a;
			w[cnt]=j*b;
            c-=j;
        }
        if(c) 
		{
			v[++cnt]=a*c;
			w[cnt]=b*c;
		}
	}
    for(int i=1;i<=cnt;i++)
   	{
   		for(int j=m;j>=w[i];j--)
   		{
   			f[j]=max(f[j],f[j-w[i]]+v[i]);
		}
	} 
    printf("%d\n",f[m]);
    return 0;
}