背包问题 ★★★

（1） 0-1 背包问题 (每样物品选1个)

题目介绍

输入样例

4 5
1 2
2 4
3 4
4 5

输出

8

[版本一] 0-1背包问题的二维状态定义

• f[i][j] : 只选前i个物品, 总体积 <= j 的 Max

状态分析

(1) 当前背包容量不够时（j < v[i]），选不了第 i 个物品，因此前i个物品的最优解和前 i - 1一样

• f[i][j] = f[i - 1][j]

(2) 当前背包容量够第 i 个时（j ≥ v[i]），可选第 i 个物品，因此需要继续决策 选 or 不选 第i个物品

• 选：f[i][j] = f[i - 1][j - v[i] + w[i]
• 不选：f[i][j] = f[i - 1][j]
• 最后取Max

状态转移方程：
f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i]

C++ 代码如下

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 1010;
int n, m;
int v[N]; // 体积
int w[N]; // weight
int f[N][N];  // DP数组
// f[i][j] : 只选前i个物品, 总体积 <= jint main(){cin >> n >> m;for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];// 二维f[i][j]    for(int i = 1; i <= n; i++){for (int j = 0; j <= m; j ++ ){f[i][j] = f[i-1][j];  // 对应情况1if(j >= v[i]) // j-v[i] >= 0  对应情况2, 并决策f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]);} // !!! f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])}cout << f[n][m] <<endl;return 0;
}

[版本二——最终版本] 0-1背包问题的一维状态

• 在分析二维状态时，第 i 轮的状态只和第 i - 1 轮有关，因此可以去掉数组第一维
• [注] : 每轮遍历 j 的过程中, i 是不变的(都是第 i 轮的状态),
  但是当前第i轮的状态需要第 i - 1 轮的状态, 所以需要逆序枚举

举个栗子：

假如枚举到：i = 3, j = 8, v[3] = 5, w[3] = 1二维：dp[3][8] = max(dp[2][8], dp[2][3] + w[3])   此时的dp[2][8]和dp[2][3]都是上一轮的状态值一维：dp[8] = max(dp[8], dp[3] + w[3])      优化一维, 需要保证dp[8]和dp[3]都是上一轮的状态值如果顺序枚举j：(第i轮) 当j = 8时, j = 3 已经枚举过了,dp[3] 已经计算过了, 因此 dp[3] 是第i轮的状态, 而不是第i-1轮的状态  ×如果逆序枚举j: (第i轮) 当j = 8时, j = 3 还未枚举dp[3] 还未计算, 因此 dp[3] 是第i-1轮的状态  √

C++ 代码如下

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 1010;
int n, m;
int v[N]; // 体积
int w[N]; // weight
int f[N];  // DP数组
// f[j] :  总体积 <= jint main(){cin >> n >> m;for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];// 优化: 一维f[j]  v[i] <= j <= Vfor(int i = 1; i <= n; i++){for(int j = m; j >= v[i]; j--){ // [注] j需要逆序f[j] = max(f[j], f[j-v[i]] + w[i]);} //f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])}cout << f[m] <<endl;return 0;
}

（2）完全背包问题 (每样物品选无限个)

题目描述

输入样例

4 5
1 2
2 4
3 4
4 5

输出

10

状态分析

版本一、暴力 (TLE)

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*v[i]);
cout<< f[n][m] <<endl;

因此需要优化状态转移方程

原 : 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-3*v]+3*w , .....)
又∵f[i , j-v]= max(-----------f[i-1,j-v] , f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)
由上两式，可得出如下递推关系：

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

对比 0-1 背包的二维转移方程, 只有下标不同

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

版本二、优化后的二维状态方程
代码如下：

for(int i = 1; i <= n; i++){for(int j = 0; j <= m; j++){// f[i][j] = max(f[i-1][j], f[i-1][j-v] + w)  0-1背包// f[i][j] = max(f[i-1][j], f[i][j-v] + w)   完全背包f[i][j] = f[i-1][j];if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);}
}
cout<< f[n][m] <<endl;

版本三——最终版：一维状态方程

• [注] : j 顺序遍历
• 因为当前第 i 轮, f[j] 的状态只需要第 i 轮 f[j - v] 的状态

完整代码如下

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 1010;int v[N], w[N];
int f[N];
int n, m;int main(){cin >> n >> m;for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];for(int i = 1; i <= n; i++){for(int j = v[i]; j <= m; j++){f[j] = max(f[j], f[j - v[i]] + w[i]);}}  cout<< f[m] <<endl;return 0;
}

（3）多重背包问题 (每样物品限制s个)

题目描述

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出

10

状态分析
版本一、暴力法

• 状态转移方程

f[i][j] = max(f[i-1][j-v[i] * k] + w[i] * k)，k 为选的个数，范围从 0 到 s[i]

• 代码如下

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

版本二、利用分组二进制的思想优化

• 利用分组和二进制优化的思想, 将每个物品的数量s 分为1, 2, 4,...,2^k, c 共 log(s) + 1 组
  数量s 一定可以由二进制数表示, 保证 s == 1 + 2 + 4 + ... + 2^k + c
  

代码如下

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 24000, M = 2010;int n, m;
int v[N], w[N], s[N];
int f[M];
int cnt = 0;int main(){cin >> n >> m;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 ; // Vw[cnt] = b * k;  // Ws -= k; // s - 2^kk *= 2; // k = k * 2}//剩余不满足2^k的一组if(s > 0) {cnt ++ ;v[cnt] = a * s; w[cnt] = b * s;}}// for(int i = 1; i <= cnt; i++){//     cout << v[i] <<" "<< w[i] <<endl;// }// 分完组后, 每个组相当于0-1背包中的一个物品// 0-1背包 一维优化for(int i = 1; i <= cnt; i++)for(int j = m; j >= v[i]; j-- )f[j] = max(f[j], f[j-v[i]] + w[i]);cout << f[m] << endl;return 0;
}

（4）分组背包问题 (每组若干个, 一组只能选1个 )

题目描述

输入样例

3 5
2
1 2
2 4
1
3 4
1
4 5

输出

8

状态分析
从第 i 组选一个, 总体积不超过 j
状态转移方程 :
f[i][j] = max(f[i-1][j], f[i-1][j-v[i][k]] + w[i][k])

[注]

• 因为第 i 轮状态依赖第 i-1 轮, 所以优化为一维的时候, j 需要逆序
• 若第 i 轮状态只依赖与 i 轮，则优化为一维的时候, j 顺序即可

代码如下

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 105;int f[N]; // f[i][j] : 从第 i 组选1个, 体积不超过 j
int v[N][N], w[N][N];
int s[N]; // 组数
int n, m;int main(){cin >> n >> m;for(int i = 1; i <= n; i ++){ // n : 总组数cin >> s[i];  // s[i] : 组内个数for(int j = 0; j < s[i]; j++){cin >> v[i][j] >> w[i][j];  // [第i组] [第j个]}}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]);cout << f[m] <<endl;return 0;
}

线性DP ★★（未完待续）

（1）数字三角形

（2）最长上升子序列 - LIS

（3）最长公共子序列 - LCS

（4）other - 最短编辑距离

区间DP

石子合并

计数DP

整数划分

记忆化搜索

滑雪