背包DP

A4paper · 2018-04-01 21:18:24 · 个人记录

这篇文章原先是叫《 01 背包 》的，但随着题目的积累，范围也不再局限于 01 背包了，所以于 2018-10-21 20:27 更名为 《 背包 DP 》

01背包方案数：

传送门

与朴素的 01背包不同，此题需输出方案数。

所以，

long m,n;
long c[100005],f[100005];

long main()
{
    cin >> n >> m;
    f[0] = 1;
    for(long i=1;i<=n;i++)  cin >> c[i];
    for(long i=1;i<=n;i++)
        for(long v=m;v>=c[i];v--)
            f[v] += f[v-c[i]];

    cout << f[m];
    return 0;
}

01背包记录路径：

传送门

这道题真心不错哎，有两个限制条件所以要开三维数组（当然，可以压去一维），而且需要需要记录路径。

路径的记录：

一，初始化：

开两个三维数组 g 、p ，一个记录当前状态对应的物品，一个记录当前状态对应的上一个物品（或者说是记录当前状态由哪一个物品转移而来），舒适化为 0

二、更新：

在状态转移的时候顺便更新两个数组，这不难理解，详见代码

三、调用：

最后一件物品必定是状态 f[n][m][v] 下对应的物品，然后顺着 p 反向找出之前的路径。

int m,v,n,x,cnt;
int a[MAXN];
int M[MAXN],V[MAXN];
int f[MAXN][MAXN][MAXN]; //背吧
int g[MAXN][MAXN][MAXN]; //记录这个状态对应物品
int p[MAXN][MAXN][MAXN]; //记录这个状态对应的上一个物品

int main(void)
{
    cin >> m >> v >> n;
    for(int i=1;i<=n;i++)
    {
        int W;
        cin >> M[i] >> V[i] >> W;
        for(int j=0;j<=m;j++)
        for(int k=0;k<=v;k++)
        {
            if(j<M[i] || k<V[i] || f[i-1][j][k]>=f[i-1][j-M[i]][k-V[i]]+W)
            {
                f[i][j][k] = f[i-1][j][k];
                g[i][j][k] = g[i-1][j][k];
            }
            else
            {
                f[i][j][k] = f[i-1][j-M[i]][k-V[i]]+W;
                p[i][j][k] = g[i-1][j-M[i]][k-V[i]];
                g[i][j][k] = i;
            }
        }
    }
    cout << f[n][m][v] << endl;
    x = g[n][m][v];
    while(p[x][m][v])
    {
        a[++cnt] = x;
        x = p[x][m][v];
        m -= M[a[cnt]];
        v -= V[a[cnt]];
    }
    a[++cnt] = x;
    for(int i=cnt;i>=1;i--)
        cout << a[i] << " ";
    return 0;
}

进阶：

传送门

本题乍一看像是用 01 背包求体积满足时，体力的最小值

01 背包没有这种操作。

所以，

应该转换一下思路：

求体力满足的情况下，最早满足体积的体力值

没毛病，不是吗？

//01背包就是体力的背包所能装的最大体积
long v,n,c;
long svi,sci;
long vi[10010],ci[10010],f[10010];//体力的背包所能装的最大体积

long main()
{
    cin >> v >> n >> c;
    for(long i=1;i<=n;i++)
    {
        cin >> vi[i] >> ci[i];
        svi += vi[i];
    }
    if(svi < v) //特判一手
    {
        cout << "Impossible";
        return 0;
    }
    for(long i=1;i<=n;i++)  //01背包
    for(long k=c;k>=ci[i];k--)
        f[k] = max(f[k],f[k-ci[i]]+vi[i]);
    if(f[c] < v)
    {
        cout << "Impossible";
        return 0;
    }
    for(long i=1;i<=c;i++)  //寻找最早满足体积的体力值
        if(f[i] >= v)
        {
            cout << c-i;
            return 0;
        }
}

高难：

传送门

很多人都是把高度作为状态，转移最大血量，

我习惯于把血量作为状态，转移最大高度，

转移方程：

f[i%2][j]=min(f[i%2][j],max(f[!(i%2)][j-w],j+e)); ①

f[i%2][j]=min(f[i%2][j],max(f[!(i%2)][j],k+e)); ②

①式的 max 表示如果前一个人的吃饭时间比第 i 个人等待+吃饭时间还长，那就不用考虑第 i 个人的耗时了，否则就是第 i 个人的等待+吃饭的耗时。

②式因为是 2 号窗口的，所以即使前一个人耗时很长，也不会对 1 号窗口的 j 有影响，直接转移。

int sum[MAXN];
int f[2][MAXN*MAXN];

struct node{
    int wait,eat;
    bool operator < (node a) const{
        return eat > a.eat;
    }
}people[MAXN];

int main(void)
{
    memset(f,0x3f,sizeof f);
    f[0][0] = 0;
    cin >> n;
    for(int i=1;i<=n;i++)
        cin >> people[i].wait >> people[i].eat;
    sort(people+1,people+1+n);
    for(int i=1;i<=n;i++)
        sum[i] = sum[i-1]+people[i].wait;
    for(int i=1;i<=n;i++)
    {
        for(int j=sum[i];j>=0;j--)  f[i%2][j] = 0x3f3f3f3f;
        for(int j=sum[i];j>=0;j--)
        {
            int w = people[i].wait;
            int e = people[i].eat;
            if(j >= w)
                f[i%2][j]=min(f[i%2][j],max(f[!(i%2)][j-w],j+e));
            int k = sum[i]-j;
            if(k >= w)
                f[i%2][j]=min(f[i%2][j],max(f[!(i%2)][j],k+e));
        }
    }
    int ans = 0x3f3f3f3f;
    for(int i=0;i<=sum[n];i++)
        ans = min(ans,f[n%2][i]);
    cout << ans;
    return 0;
}

转化：

传送门

一遍切黄，爽的一批。

这道题并不是明显的背包问题，需要进行必要的转化才能使题目变得显然。

首先，在奶牛一只一只的往船上装时，有两个限制条件：时间和奶牛数量，要在尽量少的时间内运完所有奶牛，这是不是可以隐约联想到背包呢？

那么继续跟着感觉走，如果是背包的话，要找出体积和价值（或者可以叫做花费）。

再来看一下两个限制条件：时间和数量，因为要运的奶牛数量是固定的，不能多也不能少，所以是不是可以把数量看做总体积呢？那么消耗时间就是价值咯！由于题目给出了每多一头牛增加的时间，所以一次运 i 头牛消耗的总时间要求一遍前缀和。这样想想，好像就可以用完全背包了。

void dp()
{
    for(int i=1;i<=n;i++)
    for(int j=v[i];j<=n;j++)
        f[j] = min(f[j],f[j-v[i]]+w[i]);
}

int main(void)
{
    memset(f,0x3f,sizeof f);
    cin >> n >> m;
    w[0] = 2*m;
    f[0] = 0;
    for(int i=1;i<=n;i++)
    {
        cin >> w[i];
        w[i] += w[i-1];
        v[i] = i;
    }
    dp();
    cout << f[n]-m;
    return 0;
}

综合：

传送门

01背包 + 多重背包 + 完全背包 的标准模板，有很好的参考作用。

signed main(void)
{
    cin >> n >> m;
    while(n--)
    {
        cin >> x >> A >> B;
        if(x == 1)
            for(int i=m;i>0;i--)
            for(int j=1;j<=i;j++)
                f[i] = max(f[i],f[i-j]+(j*j*A-j*B));
        if(x == 2)
        {
            cin >> C;
            for(int i=m;i>=B;i--)
            for(int j=1;j<=C;j++)
                if(i-j*B < 0) break;
                else f[i] = max(f[i],f[i-j*B]+j*A);
        }
        if(x == 3)
            for(int i=B;i<=m;i++)
                f[i] = max(f[i],f[i-B]+A);
    }
    cout << f[m];
    return 0;
}

分组背包：

传送门

和 01 背包类似，只是同组物品只能选一个，所以要在枚举背包容量的循环之后再加一个循环枚举第 i 组的物品

int n,m,cnt;
int v[MAXN],w[MAXN],group[MAXN];
int f[MAXN];
int id[MAXN][MAXN]; //表示第 i 组第 j 个物品的序号

signed main(void)
{
    cin >> m >> n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin >> v[i] >> w[i] >> x;
        cnt = max(cnt,x);
        group[x]++;
        id[x][group[x]] = i;
    }
    for(int i=1;i<=cnt;i++)  //枚举组
    for(int j=m;j>=0;j--)   //枚举背包容量
    for(int k=1;k<=group[i];k++) //枚举 i 组的物品
    {
        int a = id[i][k];
        if(j >= v[a])
            f[j] = max(f[j],f[j-v[a]]+w[a]);
    }
    cout << f[m];
    return 0;
}

分组背包方案数：

传送门

经过观察发现，与上面一道分组背包相比，两者三重循环的顺序不同，这道题是先枚举了第 i 组每个物品 &j& 后再枚举的背包容量，为什么呢？

由于题意不同（废话！）

这道题需要统计所有可能的方案数，所以不能仅仅在每组中选取一个最优的物品，要枚举所有物品，对，枚举~

int n,m,p,tot,cnt;
int a[105][10005];
int f[105][10005];

int main(void)
{
    cin >> n >> p;
    for(int i=1;i<=n;i++)
    {
        int num;
        cin >> num;
        cnt = 0;
        a[i][0] = num;
        for(int j=1;j<=num;j++)
        {
            cin >> a[i][j];
            cnt = max(cnt,a[i][j]);
        }
        tot += cnt;
    }
    f[0][0] = 1;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=a[i][0];j++)
    for(int k=tot;k>=a[i][j];k--)
        f[i][k] += f[i-1][k-a[i][j]];
    cnt = 0;
    for(int j=1;j<=tot;j++)
    for(int k=1;k<=f[n][j];k++)
    {
        cout << j << " ";
        cnt++;
        if(cnt == p) return 0;
    }
    return 0;
}

树上 分组 01 背包：

传送门

结合树形 DP

将每个儿子的 size 求出枚举选取儿子的个数之后跑 01，

int f[MAXN][MAXN];  // f[i][j] 表示以 i 为根选取 j 个点的最大值 

int dp(int u, int fa)
{
    if(u<=n && u>n-m)   return 1;
    int tot = 0;
    for(int k=head[u];k;k=tree[k].next)
    {
        int v = tree[k].to;
        int w = tree[k].w;
        if(v == fa) continue;
        int size = dp(v,u);
        tot += size;
        for(int i=tot;i>=0;i--)
        for(int j=1;j<=size && i>=j;j++)
            f[u][i] = max(f[u][i],f[u][i-j]+f[v][j]-w);
    }
    return tot;
}

int main(void)
{
    cin >> n >> m;
    memset(f,0x80,sizeof f);
    for(int i=1;i<=n;i++)   f[i][0] = 0;
    for(int i=1,num;i<=n-m;i++)
    {
        cin >> num;
        for(int j=1;j<=num;j++)
        {
            cin >> A >> C;
            add(i,A,C); add(A,i,C);
        }
    }
    for(int i=n-m+1;i<=n;i++)
    {
        cin >> val[i];
        f[i][1] = val[i];
    }
    dp(1,0);
    for(int i=m;i>0;i--)
        if(f[1][i] >= 0)
        {
            cout << i;
            return 0;
        }
    return 0;
}

变式：

传送门

这道题很清楚明白的展示了树上背包的大概套路。

不过，输入真的很迷人，第一次被输入卡。。。本来打算先递归输入，然后再跑树上背包的，但是发现似乎行不通。。。所以决定边跑边输入。

思路还是蛮清晰的，就是要以时间为背包容量，在每个房间跑 01 背包，然后对于每个非叶节点枚举最大值。

详见代码吧！

int n,tot;//tot为节点编号
int f[MAXN][MAXN];
//f[i][j] 表示在点i用了j秒的最大价值。

void dfs_read(int x)
{
    int t,w;
    cin >> t >> w;t *= 2;
    if(w)//房间有画
    {
        int v,s;
        for(int i=1;i<=w;i++)//这是01背包，
        {//在有画的房间跑01记对于每个时刻能获得的最大值
            cin >> v >> s;
            for(int j=n;j>=s+t;j--)//s+t为偷画的时间和通过走廊的时间，这必是最小值
                f[x][j] = max(f[x][j],f[x][j-s]+v);
        }
    }
    else//连接另外两个走廊
    {
        tot++;int p1=tot;dfs_read(tot);//一定要记下当前节点编号！（被坑死了）
        tot++;int p2=tot;dfs_read(tot);//接下来合并两个子树的答案。
        for(int i=t;i<=n;i++)//枚举在当前点还剩的时间（至少为t，因为走到走廊尽头还需t秒）
        for(int j=0;j<=i-t;j++)//枚举分给左右子树的时间
            f[x][i] = max(f[x][i],f[p1][j]+f[p2][i-t-j]);
    }
}

signed main(void)
{
    cin >> n;n--; //这里要减一（毒瘤！）
    dfs_read(++tot);
    cout << f[1][n];
    return 0;
}