本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-11-23 21:07:16

P1048 [NOIP2005 普及组] 采药

难度：$\color{orange}\text{普及-}$

$\color{green}\text{AC算法：01背包}$

题目分析：

题目转化：有 $m$ 个物品，价值为 $w[i]$，大小为 $t[i]$。总容量大小为 $t$.
可以设一个状态 $dpm[i][j]$，代表当前已经确定 $i$ 个物品且当前空间为 $j$ 时的最大价值。那么转移方程显然为：

dpm[i][j]=max(dpm[i-1][j],dpm[i-1][j-ti[i]]+w[i]);

$dpm[i-1][j]$ 代表之前已经确定了 $i-1$ 个物品，空间为 $j$。且不放置当前物品时的最大价值。$dp[i-1][j-ti[i]]$ 代表之前已经确定了 $i-1$ 个物品，放置了当前物品的情况。既然放置了当前物品，那么之前的空间肯定是 $j-ti[i]$ 。（此时可以发现前面都是i-1，所以可以直接砍掉第一个数组维度，进行滚动数组优化）

放上$\color{green}\text{AC}$代码：

#include <bits\/stdc++.h>
using namespace std;
#define reg register 
int t,m;
int w[1005];
int ti[1005];
int dpm[1005];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void dp()
{
    for(int i=1;i<=m;i++)
    {
        for(int j=t;j>=ti[i];j--)
        {
            \/\/如果不使用滚动数组，那么就是：
            \/\/dpm[i][j]=max(dpm[i-1][j],dpm[i-1][j-ti[i]]+w[i]);
            \/\/意思是选择了i个，且当前容量为j的最大价值
            dpm[j]=max(dpm[j],dpm[j-ti[i]]+w[i]);
        }
    }
}
int main()
{
    t=read();
    m=read();
    for(reg int i=1;i<=m;i++)
    {
        ti[i]=read();
        w[i]=read();
    }
    dp();
    printf("%d",dpm[t]);
    return 0;
}

P1616 疯狂的采药

难度：$\color{orange}\text{普及-}$

$\color{green}\text{AC算法：完全背包}$

题目分析：

本题与01背包类似，只是变成了每种有无限个。但是此时状态转移方程却还是原来那个：$dpm[j]=max(dpm[j],dpm[j-ti[i]]$，此时仅仅是枚举空间大小的顺序和01背包相反，因为从小到大枚举时，例如首先更新了$dpm[j-3ti[i]]$的最大价值，然后空间向上枚举了ti[i]后，就相当于使用$dpm[j-3ti[i]]$去更新$dpm[j-3ti[i]+ti[i]]$，也就是$dpm[j-2ti[i]]$，以此类推，直到更新$dpm[j]$的最大价值。（此时和01背包一样使用了滚动数组优化）

放上$\color{green}\text{AC}$代码：

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
#define reg register 
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
const int maxn=1e4+5;
const int maxdp=1e7+5;
int t,m;
int ti[maxn];
int w[maxn];
ll dpm[maxdp];
inline void dp()
{
    for(reg int i=1;i<=m;i++)
    {
        for(int j=ti[i];j<=t;j++)
        {
            dpm[j]=max(dpm[j],dpm[j-ti[i]]+w[i]);
        }
    }
}
signed main()
{
    t=read();
    m=read();
    for(reg int i=1;i<=m;i++)
    {
        ti[i]=read();
        w[i]=read();
    }
    dp();
    printf("%lld",dpm[t]);
    return 0;
}

P1776 宝物筛

难度：$\color{green}\text{ 普及+/提高}$

$\color{green}\text{AC算法：多重背包}$

题目分析：

题目转化：
给一个大小为 $W$的背包，共有 $n$ 种物品,每种有 $m[i]$ 件，价值为 $v[i]$，大小为 $w[i]$。问能获得的最大价值。
可以发现，它与01背包不同之处在于它一个物品有多个。这样就可以把第 $m[i]$ 种物品拆分成 $m[i]$个物品，枚举k为$(1 \rightarrow\ m[i])$即可。那么转移方程就为： $f[j]=max(f[j],f[j-w[i]k]+v[i]k)$
其中 $j$ 代表01背包当前空间为 $j$ ， $i$ 代表这是第 $i$ 个物品 。
但是这样复杂度就太高了 可以使用二进制拆分。将其拆分成大小分别为$1,2,4,8.....m[i]$的物品,如果最后有剩余那么将剩余的作为一个物品，可以发现，拆分出来的这些物品能组成 $1 \rightarrow\ m[i]$ 中的任何数，所以分别对拆分出来的每一个物品跑01背包，一定能求出最优解。

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
#define reg register
int n,W;\/\/背包大小为W
const int maxn=1e5+5;
const int maxw=4e4+5;
int v[maxn];\/\/价值
int w[maxn];\/\/重量
int m[maxn];\/\/m件
int f[maxn];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void dp()
{
    for(reg int i=1;i<=n;i++)
    {
        int mi=m[i];
        int wi=w[i],vi=v[i];
        int pkg=1;
        while(mi>pkg)
        {
            mi-=pkg;
            wi=w[i]*pkg;
            vi=v[i]*pkg;
            for(reg int j=W;j>=wi;j--)
            {
                f[j]=max(f[j],f[j-wi]+vi);
            }
            pkg*=2;
        }
        wi=w[i]*mi;
        vi=v[i]*mi;
        for(reg int j=W;j>=wi;j--)
        {
            f[j]=max(f[j],f[j-wi]+vi);
        }
    }
}
int main()
{
    n=read();
    W=read();
    for(reg int i=1;i<=n;i++)
    {
        v[i]=read();
        w[i]=read();
        m[i]=read();
    }
    dp();
    printf("%d",f[W]);
    return 0;
}