背包问题（一）

背包模型

前置母题

01背包问题

\(有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。\)

状态表示

集合

所有只考虑前\(i\)个物品，且总体积不超过\(j\)的选法的合集
属性

\(Max\)

状态计算

划分为两类，一类为所有不选第\(i\)个物品的方法，另一类为选第\(i\)个物品的选法

得到转移方程

\[f[i][j] = max(f[i-1][j],f[i-1][j-v] + w) \]

Code

朴素写法

for (int i = 1; i <= n; ++i)
    	for (int j = 0; j <= m; ++j)
            	if (j < v[i]) f[i][j] = f[i-1][j];
				else f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i]);

空间优化

根据转移方程，可以看出每层的状态转移最多只用到上一层的状态，所以可以将空间从\(O(n·m)变成O（m）\)，需要注意的是，此处需要逆序遍历，因为在本层更新前，数组内存储的是上一层的DP结果，当我们更新较大的DP数值的时候，需要用到上一层的DP数值，所以此处需要逆序遍历。
```
for (int i = 1; i <= n; ++i)
    	for(int j = m; j >= v[i]; --j)
				f[j] = max(f[j-v[i]] + w[i], f[j]);
```

进一步空间优化

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

完全背包问题

\(有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。\)

状态表示

集合

从前\(i\)种物品中选取，且总体积不超过\(j\)的所有选法
属性

\(Max\)

状态计算

根据第\(i\)个物品选取多少个来进行集合的划分，可以得到状态转移方程。

\[f[i][j] =max(f[i-1][j-k*v]+k*w)\\(k*v<=j) \]

Code

朴素版本

for (int i = 1; i <= n; ++i) 
    for (int j = 0; j <= m; ++j) 
        for (int k = 0; k*v[i] <= j; ++k)
            	f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

优化过程

规律

f[i][j] = max(f[i-1][j], f[i-1][j-v]+w, f[i-1][j-2*v]+2*w...f[i-1][j-k*v] + k*w)
f[i-1][j-v] = max(       f[i-1][j-v],   f[i-1][j-2*v]+w ....f[i-1][j-k*v] + (k-1)*w)

得到优化的转移方程

\[f[i][j]=max(f[i-1][j],f[i][j-v]+w) \]

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

进一步优化

与01背包极为相似，只在遍历顺序不同，从转移方程中可以看出我们需要的是同一层的数组元素，逆序更新的话会对数据造成污染。
```
for (int i = 1, v, w; i <= n; ++i) {
    std::cin >> v >> w;
    for (int j = v; j <= m; ++j)
		f[j] = max(f[j], f[j-v[i]]+w[i]);
}
```
其实想想也是，01背包每个物品只能选一个，如果从小往大选，在体积增大的时候，会造成对同一个物品选两次的可能性。

多重背包I

\(有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 s_i件，每件体积是 v_i，价值是 w_i。\)

状态表示

集合

所有只从前\(i\)个物品里选，并且总体积不超过\(j\)的选法的集合
属性

\(Max\)

状态计算

参考01背包思路，我们对集合进行划分，每一子集为对该类物品选了若干个，每次选或不选两种操作。

即得到转移方程

\[f[i][j]=max(f[i-1][j-k*v]+w*k,f[i-1][j])\\ k \in0,1,2,3,4...s_i \]

Code

朴素版本

for (int i = 1; i <= n; ++i) 
    for (int j = 0; j <= m; ++j) 
        for (int k = 0; k*v[i] <= j; ++k)
            f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

空间优化

通过观察转移方程，可以看到，我们每次更新只和本层和上一层存储的数组元素有关。

此处需要逆序操作，还是因为需要保证上一层数据的纯净。
```
for (int i = 1,v ,w, s; i <= n; ++i) {
    std::cin >> v >> w >> s;
    for (int j = m; j >= v; --j)
        for (int k = 1; k <= s && k*v <= j; ++k)
            f[j] = max(f[j], f[j-k*v]+k*w);
}
```
f[j]表示体积为j时候的最优解。

多重背包问题Ⅱ

\(有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 s_i件，每件体积是 v_i，价值是 w_i\)

二进制优化

对于每种物品，以二进制的形式进行一个打包成一个新的物品，将问题转化为01背包问题，对每个新物品进行选或不选两种操作，用该方法可以完全枚举选取\(0-s_i\)的所有选法。

Code

二进制优化+01背包一维优化

int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        int a,b,s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s) {
            cnt ++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if (s > 0) {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    n = cnt;
    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[j] = max(f[j], f[j-k*v]+k*w) \]

我们可以将它正序过来，则有以下状态

\[f[m] = max(f[0], f[v]+w, f[2*v]+2*w... f[k*v+j]+k*w)\\ m = k*v+j\\ 0<=j

不难发现，每一类中的最大值都是在同一层的DP数组中转移而来，在这里可以使用单调队列进行优化，最后求取单调队列中的最大值。

Code-\(O(nv)\)

朴素写法

for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < v[i]; ++j) {
        int hh = 0, tt = -1;
        for (int k = j; k <= m; k += v[i]) {
            while (hh <= tt && k - q[hh] > s[i] * v[i]) ++hh;
            while (hh <= tt && f[i-1][q[tt]] + (k - q[tt])/v[i])
                q[++tt] = k;
            f[i][j] = f[i-1][q[hh]] + (k - q[hh])/v[i] * w[i];
        }
    }
}

拷贝数组写法

for (int i = 1; i <= n; ++i) {
    int v, w, s; std::cin >> v >> w >> s;
    for (int j = 0; j < v; ++j) {
        int hh = 0, tt = -1;
        for (int k = j; k <= m; k += v) {
            if (hh <= tt && q[hh] <= k - s * v) ++hh;
             while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) --tt;
                q[ ++ tt] = k;
                f[k] = g[q[hh]] + (k - q[hh]) / v * w;
        }
    }
}

分组背包

\[有 N 组物品和一个容量是 V 的背包。\\ 每组物品有若干个，同一组内的物品最多只能选一个。\\ 每件物品的体积是 v_{ij}，价值是 w_{i,j}，其中i是组号,j是组内编号。 \]

状态表示

集合

从前\(i\)组中选，每组从前\(k\)个物品里选且总体积小于\(j\)的所有选法
属性

\(Max\)

状态计算

分成若干组，按照01背包进行计算，每组选或不选两种情况。

\(f[i][j] = f[i-1][j]\)
不选

\(f[i][j] = f[i-1][j-v_{ik}]+w_{ik}\)

Code

朴素版本

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

优化版本

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

动态规划学习

背包问题（一）

背包模型

前置母题

01背包问题

状态表示

状态计算

Code

完全背包问题

状态表示

状态计算

Code

多重背包I

状态表示

状态计算

Code

多重背包问题Ⅱ

二进制优化

Code

多重背包Ⅲ

基于滑动窗口优化

Code-\(O(nv)\)

分组背包

状态表示

状态计算

Code

相关

标签