背包dp复习

· · 个人记录

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]);
#### 放上$\color{green}\text{AC}$代码： ```cpp #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-3*ti[i]]的最大价值，然后空间向上枚举了ti[i]后，就相当于使用dpm[j-3*ti[i]]去更新dpm[j-3*ti[i]+ti[i]]，也就是dpm[j-2*ti[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;
}