背包DP

Last_Reincarnation · 2019-10-21 17:00:13 · 个人记录

来源

动态规划应用于子问题重叠的情况：

1.要去刻画最优解的结构特征；

2.尝试递归地定义最优解的值（就是我们常说的考虑从 转移到 ）；

3.计算最优解；

4.利用计算出的信息构造一个最优解。

1. 0-1 背包

[USACO07DEC]手链Charm Bracelet

有N件物品和一个容量为V的背包。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

code

#include<iostream>
#include<cstdio>
using namespace std;

const int maxn = 20010;

int m, n;
int f[maxn], t[maxn], v[maxn];

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1;i <= n; ++i)
        scanf("%d%d", &t[i], &v[i]);
    for (int i = 1;i <= n; ++i){
        for (int j = m;j >= t[i]; --j)
            f[j] = max (f[j], f[j-t[i]] + v[i]);
        }
    printf("%d",f[m]);
}

在上述例题中，由于每个物体只有2种可能的状态（取与不取），正如二进制中的 和0和1这类问题便被称为“0-1 背包问题”。

例题中已知第i件物品的wi，vi，以及背包总容量m

设f ij 为在只能放前i个物品的情况下，容量为j的背包所能达到的最大总价值。

考虑转移。假设当前已经处理好了前i-1个物品的所有状态，那么对于第i个物品，当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 f[i][j]；当其放入背包时，背包的剩余容量会减小 v[i] ，背包中物品的总价值会增大 w[i] ，故这种情况的最大价值为 f[i][j-v[i]] + w[i]。

所以状态转移方程为 f[i][j] = max (f[i][j], f[i-1][j-v[i]] + w[i]);

在程序实现的时候，由于对当前状态有影响的只有f[i-1]，故可以去掉第一维，直接用 f[i] 来表示处理到当前物品时背包容量为 的最大价值，得出以下方程： f[i] = max (f[i], f[j-v[i]] + w[i]);

最后枚举顺序一定要正确。仔细观察代码可以发现：对于当前处理的物品i和当前状态 f[i][j] ，在 j>=w[i] 时, f[i][j] 是会被 f[i][j-v[i]] 所影响的。这就相当于物品i可以多次被放入背包，与题意不符。（事实上，这正是完全背包问题的解法）

为了避免这种情况发生，我们可以改变枚举的顺序，从m枚举到w[i]，这样就不会出现上述的错误，因为 f[i][j] 总是在 f[i][j-v[i]]前被更新。 因此实际核心代码为

    for (int i = 1;i <= n; ++i){
        for (int j = m;j >= v[i]; --j)
            f[j] = max (f[j], f[j-v[i]] + w[i]);
        }

初始化的细节问题:

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。 有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法，要求恰好装满背包，那么在初始化时除了F[0] 为0，其它 F[1..V] 均设为-∞，这样就可以保证最终得到的 F[V] 是一种恰好装满背包的最优解。 如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将F[0..V]全部设为0。

这是为什么呢？可以这样理解：初始化的 F 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为 -∞ 了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 0 ，所以初始时状态的值也就全部为0了。

常数小优化

可以改第二重循环的下限。它可以被优化为

for (register int i = 1;i <= n; ++i)
    sum[i] = sum[i-1] + v[i];

for (register int i = 1;i <= n; ++i) 
    for (register int j = m;j >= max(sum[n]-sum[i-1], v[i]); --j)

这里的max优化就是考虑了这样一种情况：

即使后面(i…n)的所有物品都被装入背包后，剩余的空间仍然比 Ci 大。这个优化对 m 比较大

小结

    for (register int i = 1;i <= n; ++i){
        read(w[i]);
        read(v[i]);
        read(c[i]);
        for (register int j = 1;j <= c[i]; ++j){
            for (register int k = m;k >= v[i]; --k)
                f[k] = Max (f[k], f[k-v[i]] + w[i]);
        }
    }
    printf ("%d\n", f[m]);

虽然我们失败了，但是这个朴素的想法可以给我们的思路提供一些借鉴——我们可以把多重背包转化成 0-1 背包模型来求解。

但是发挥人类的智慧，发现2^0, 2^1, 2^2，……，2^k 从这k个2的整数次幂中选若干个相加，可以表示出0到2^k - 1之间的任何数。

举个例子

3 = 1 + 2
5 = 1 + 4
6 = 2 + 4
7 = 1 + 2 + 4
8 = 1 + 2 + 4 + 1(这里缺一个1)

显然，通过上述拆分方式，可以表示任意<=c[i]个物品的等效选择方式。将每种物品按照上述方式拆分后，使用 0-1 背包的方法解决即可。

这样就将第i种物品分成了O(log ki)种物品，将原问题转化为了复杂度为O(V Σlog ki)的01背包问题，是很大的改进。

code

    for (register int i = 1;i <= n; ++i){
        read(w[i]);
        read(v[i]);
        read(c[i]);
        for (register int j = 1;j <= c[i]; j <<= 1){
            for (register int k = m;k >= j * v[i]; --k)
                f[k] = Max (f[k], f[k-j*v[i]] + j * w[i]);
            c[i] -= j;
        }
        if (c[i]){//上述例子中的8还缺个1，这里处理
            for (register int k = m;k >= c[i] * v[i]; --k){
                f[k] = Max (f[k], f[k-c[i]*v[i]] + c[i]*w[i]);
            }
        }
    }
    printf ("%d\n", f[m]);

例题 ： P1776 宝物筛选_NOI导刊2010提高（02）

题意概要：有n种物品和一个容量为m的背包，每种物品有c[i]个，同时每个物品有两种属性：重量w和价值v。要求选若干个物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。有一点需要注意的是本题数据范围较大，情况较多。

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

const int maxn = 200;
const int N = 4e4 + 10;

int n, m;
int v[maxn], w[maxn], c[maxn];
int f[N];

int f_;
char ch_;
template <class T>
    inline T read(T &x_){
        x_ = 0, f_ = 1, ch_ = getchar();
        while (!isdigit(ch_)) {if (ch_ == '-') f_ = -1; ch_ = getchar();}
        while (isdigit(ch_)){x_ = (x_ << 3) + (x_ << 1) + ch_ - 48; ch_ = getchar();}
        return x_ *= f_;
    }

inline int Max (int x, int y){
    return (x > y) ? x : y;
}

int main(){
    read(n);
    read(m);
    for (register int i = 1;i <= n; ++i){
        read(w[i]);
        read(v[i]);
        read(c[i]);
        for (register int j = 1;j <= c[i]; j <<= 1){
            for (register int k = m;k >= j * v[i]; --k)
                f[k] = Max (f[k], f[k-j*v[i]] + j * w[i]);
            c[i] -= j;
        }
        if (c[i]){
            for (register int k = m;k >= c[i] * v[i]; --k){
                f[k] = Max (f[k], f[k-c[i]*v[i]] + c[i]*w[i]);
            }
        }
    }
    printf ("%d\n", f[m]);
    return 0;
}

当问题是“每种有若干件的物品能否填满给定容量的背包”，只须考虑填满背包的可行性，不需考虑每件物品的价值时，多重背包问题同样有O(mn)复杂度的算法。

例如，可以使用单调队列的数据结构，优化基本算法的状态转移方程，使每个状态的值可以以均摊O(1)的时间求解。(我不会)

下面介绍一种实现较为简单的O(nm)复杂度解多重背包问题的算法。它的基本思想是这样的：设F[i, j]表示“用了前i种物品填满容量为j的背包后，最多还剩下几个第i种物品可用”，如果F[i, j] = -1则说明这种状态不可行，若可行应满足0 ≤ F[i, j] ≤ ci。递推求F[i, j]的伪代码如下：

memset(f, -1, sizeof (f));
f[0] = 0; 
for (register int i = 1;i <= n; ++i){
    for (register int j = 0;j <= m; ++j){
        if (f[i-1][j] >= 0) f[i][j] = c[i];//前一个物品装满了 
        else f[i][j] = -1;
    }
    for (register int j = 0;j <= (m-v[i]); ++j){
        if (f[i][j])
            f[i][j+v[i]] = max (f[i][j+v[i]], f[i][j] - 1);//选或不选，和0_1一样 
    }
}
最终f[N][0...V ]便是多重背包可行性问题的答案。

4. 混合背包

混合背包就是将前面三种的背包问题混合起来，有的只能取一次，有的能取无限次，有的只能取c[i]次。

这种题目看起来很吓人，可是只要领悟了前面几种背包的中心思想，并将其合并在一起就可以了。下面给出伪代码：

for (循环物品种类) {
    if (是 0 - 1 背包)
        套用 0 - 1 背包代码;
    else if (是完全背包)
        套用完全背包代码;
    else if (是多重背包)
        套用多重背包代码;
}

例题：P1833 樱花

code

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

const int maxn = 10010;

int a, b, c, d, n, t, ans;
int v[maxn], w[maxn], p[maxn], f[1010];
char ch;

int f_;
char ch_;
template <class T>
    inline T read(T &x_){
        x_ = 0, f_ = 1, ch_ = getchar();
        while (!isdigit(ch_)) {if (ch_ == '-') f_ = -1; ch_ = getchar();}
        while (isdigit(ch_)){x_ = (x_ << 3) + (x_ << 1) + ch_ - 48; ch_ = getchar();}
        return x_ *= f_;
    }

inline int Max (int x, int y){
    return (x > y) ? x : y;
}

int main(){
    read(a); scanf ("%s", ch); read(b);
    read(c); scanf ("%s", ch); read(d);
    t = (c - a - 1) * 60 + 60 + d - b;
    read(n);
    for (register int i = 1;i <= n; ++i){
        read(v[i]);
        read(w[i]);
        read(p[i]);
    }
    for (register int i = 1;i <= n; ++i){
        if (!p[i]){
            for (register int j = v[i];j <= t; ++j)
                f[j] = Max (f[j], f[j-v[i]] + w[i]);
        }
        else {
             for (register int j = 1;j <= p[i]; j <<= 1){
                for (register int k = t;k >= j * v[i]; --k)
                    f[k] = Max (f[k], f[k-v[i]*j] + w[i] * j);
                p[i] -= j;
             }
             if (p[i]) {
                for (register int k = t;k >= v[i] * p[i]; --k)
                    f[k] = Max (f[k], f[k-v[i]*p[i]] + w[i] * p[i]);
             }
        }
    }
    printf ("%d\n", f[t]);
    return 0;
}

5. 二维费用背包

例题：P1855 榨取kkksc03

这道题是很明显的 0-1 背包问题，可是不同的是选一个物品会消耗两种价值（经费、时间）。这种问题其实很简单：方程基本不用变，只需再开一维数组，同时转移两个价值就行了！（完全、多重背包同理）

这时候就要注意，再开一维存放物品编号就不合适了，因为容易 MLE。

例题核心代码：

    for (register int k = 1;k <= n; ++k){
        for (register int i = M;i >= m[k]; --i)//对经费进行一层枚举
            for (register int j = T;j >= t[k]; --j){//对时间进行一层枚举
                f[i][j] = Max (f[i][j], f[i-m[k]][j-t[k]] + 1);
            }
    }

物品总个数的限制

有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取 U 件物品。这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为 1 ，可以付出的最大件数费用为U。换句话说，设F[m, u]表示付出费用 m 、最多选 u 件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的方法循环更新，最后在f[0..V, 0..U]范围内寻找答案。

小结

当发现由熟悉的动态规划题目变形得来的题目时，在原来的状态中加一维以满足新的限制是一种比较通用的方法。

6. 分组背包

例题：P1757 通天之分组背包

所谓分组背包，就是将物品分组，每组的物品相互冲突，最多只能选一个物品放进去。

这种题怎么想呢？其实是从“在所有物品中选择一件”变成了“从当前组中选择一件”，于是就对每一组进行一次0-1 背包就可以了。

然后核心代码

    for (int i = 1;i <= sum; ++i)    //循环每一组
        for (int j = m;j >= 0; --j)  //循环背包容量
            for (int k = 1;k <= t[i]; ++k){ //循环该组的每一个物品
                if(j >= v[c[i][k]])
                    f[j]=max (f[j], f[j-v[c[i][k]]] + w[c[i][k]]);//像0-1背包一样状态转移
        }

这里要注意： 一定不能搞错循环顺序 ，这样才能保证正确性。

7. 有依赖的背包

例题：P1064 金明的预算方案

简化问题

这种背包问题的物品间存在某种“依赖”的关系。也就是说，物品i依赖于物品j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。

算法

按照背包问题的一般思路，仅考虑一个主件和它的附件集合。可是，可用的策略非常多，包括：一个也不选，仅选择主件，选择主件后再选择一个附件，选择主件后再选择两个附件……无法用状态转移方程来表示如此多的策略。事实上，设有n个附件，则策略有2^n + 1个，为指数级。

考虑到所有这些策略都是互斥的（也就是说，你只能选择一种策略），所以一个主件和它的附件集合实际上对应于一个物品组，每个选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物品，其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法，因为物品组中的物品还是像原问题的策略一样多。

所以用01背包处理出每一种附件选其和其对应的一个主件的值，将其和其主件合成的物品组看成一个物品， 然后就将其转化成了分组背包。(据说这道题可以可以分类讨论然后跑01背包)

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

const int maxn = 65;

int n, m, ans;
int t[maxn], cnt[maxn];
int v[maxn][maxn], w[maxn][maxn];
int f[32100];

struct node{
    int v, w, op;
}a[maxn], belong[maxn][maxn];

int main(){
    cin >> m >> n;
    for (register int i = 1;i <= n; ++i){
        cin >> a[i].v >> a[i].w >> a[i].op;
        if (a[i].op){//附件 
            t[a[i].op]++;//主件的附件个数 
            belong[a[i].op][t[a[i].op]].v = a[i].v;
            belong[a[i].op][t[a[i].op]].w = a[i].w;
            belong[a[i].op][t[a[i].op]].op = a[i].op;
        }
    }
    for (register int i = 1;i <= n; ++i){//0_1 
        if (t[i]){
            memset(f, -1, sizeof (f));//恰好背包的处理，-1表示不恰好取到此价值
            f[0] = 0;
            for (register int j = 1;j <= t[i]; ++j){
                for (register int k = m-a[i].v;k >= belong[i][j].v; --k)
                    if (f[k] < f[k-belong[i][j].v] + belong[i][j].v*belong[i][j].w && f[k-belong[i][j].v] != -1)
                        f[k] = f[k-belong[i][j].v] + belong[i][j].v*belong[i][j].w;
            }
            for (register int j = 0;j <= m-a[i].v; ++j){
                if (f[j] != -1){
                    cnt[i]++;
                    v[i][cnt[i]] = j + a[i].v;
                    w[i][cnt[i]] = f[j] + a[i].v * a[i].w;//附件的前提是选上主件 
                }
            }
        }
        if (!a[i].op){//只买主件 
            cnt[i]++;
            v[i][cnt[i]] = a[i].v;
            w[i][cnt[i]] = a[i].v * a[i].w; 
        }
    }
    memset(f, 0, sizeof (f)); 
    for (register int i = 1;i <= n; ++i){//分组 
        for (register int j = m;j >= 0; --j)
            for (register int k = 1;k <= cnt[i]; ++k){
                if (j >= v[i][k])
                    f[j] = max (f[j], f[j-v[i][k]] + w[i][k]); 
            }
    }
    for (register int i = 0;i <= m; ++i)
        ans = max(ans, f[i]); 
    cout << ans << '\n';
    return 0;
}

较一般的问题

更一般的问题是：依赖关系以图论中“森林”3的形式给出。也就是说，主件的附件仍然可以具有自己的附件集合。限制只是每个物品最多只依赖于一个物品（只有一个主件）且不出现循环依赖。

解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是，由于附件可能还有附件，就不能将每个附件都看作一个一般的01背包中的物品了。若这个附件也有附件集合，则它必定要被先转化为物品组，然后用分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。

事实上，这是一种树形动态规划，其特点是，在用动态规划求每个父节点的属性之前，需要对它的各个儿子的属性进行一次动态规划式的求值。这已经触及到了“泛化物品”的思想。其实这个“依赖关系树”每一个子树都等价于一件泛化物品，求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。

8. 泛化物品

这种背包，没有固定的费用和价值，它的价值是随着分配给它的费用而定。在背包容量为V的背包问题中，当分配给它的费用为vi 时，能得到的价值就是h(vi)。这时，将固定的价值换成函数的引用即可。

泛化物品的和

如果给定了两个泛化物品h和l，要用一定的费用从这两个泛化物品中得到最大的价值，这个问题怎么求呢？事实上，对于一个给定的费用v，只需枚举将这个费用如何分配给两个泛化物品就可以了。同样的，对于0...V 中的每一个整数v，可以求得费用v分配到h和l中的最大价值f(v)。也即