文章目录
一、算法图解
1、背包问题
1.1 最近红红买了个新背包，但是这个新背包的容量只有4磅，装入什么可使背包中物品的价值最大
可选择的物品：
让我们浅浅地列个表格吧
网格最初是空的，你将填充其中的每个单元格
网格的各行为商品，各列为不同容量（1～4磅）的背包
此时你很可能心存疑惑：原来的问题说的是4磅的背包，我们为何要考虑容量为1磅、2磅等的背包呢？
因为动态规划从小问题着手，逐步解决大问题。这里解决的子问题将帮助你解决大问题
在每一行，可选择的商品都为当前行的商品以及之前各行的商品
公式（伪代码）：
- 你可以使用这个公式来计算每个单元格的价值，最终的网格将与前一个网格相同。
- 现在你明白了为何要求解子问题吧？你可以合并两个子问题的解来得到更大问题的解
1.2 背包问题Q&A
1.2.1 再增加一件可选商品如何呢？
再增加一件iphone
- 不可能。每次迭代时，你存储的都是 当前的最大价值。
- 划重点：在每一行，可偷的商品都为当前行的商品以及之前各行的商品
- 最后一行之前，没有偷到iphone，最大价值的物品中 还不包含iphone
最大价值不可能比以前低！
1.2.2 行的排列顺序 发生变化时结果将如何
答案会随之变化吗？假设你按如下顺序填充各行：音响、笔记本电脑、吉他。网格将会是什么样的？
答案没有变化。也就是说，各行的排列顺序无关紧要。
1.2.3 旅游行程最优化
最近红红放假了，他决定去欧洲旅游，但是假期只有两天，没法将所有景点去完，因此尽量选择评分最高的景点，请帮红红选出最优旅游行程
约束条件不是背包的容量，而是有限的时间；不是决定该装入哪些商品，而是决定该去游览哪些名胜
1.2.4 处理相互依赖的情况
上述旅游清单中添加几项
单独玩时：
- 这3个地方都玩需要的总时间为3.5天 这种有依赖捆绑关系的事件，无法用动态规划解决
但仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。
2、最长公共子串
2.1 找出单词hish和fish的最长公共子串
- 红红想查单词fish，但不小心输入了hish。在你的字典中，根本就没有这样的单词，但有几个类似的单词。那他原本要输入的是fish还是vista呢？
- 那么hish和fish都包含的最长子串是多少个字母？hish和vista呢？
每个单元格都是一个子问题的值
公式：
- 对于前面的背包问题，最终答案总是在最后的单元格中。
- 但对于最长公共子串问题，答案为网格中最大的数字——它可能并不位于最后的单元格中
我们回到最初的问题：哪个单词与hish更像？
hish和fish的最长公共子串包含三个字母，而hish和vista的最长公共子串包含两个字母。
因此红红很可能原本要输入的是fish
3、最长公共子序列
3.1 假设红红不小心输入了fosh，他原本想输入的是fish还是fort呢？
- 最长公共子串的长度相同，都包含两个字母！
- 但fosh与fish更像，有3个公共字母，而fort 和forsh只要2个公共字母
计算最长公共子序列的表格：
这个表格是什么意思？怎么列出来的嘞？
最终表格：
公式（伪代码）：
二、题目/代码
1、背包问题
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。 接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i
件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N, V≤1000， 0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8
公式：
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]);
AC代码：
#include<iostream>
using namespace std;
int n,m;
const int N=1010;
int v[N],w[N];
int f[N][N];
int main()
{
cin>>n>>m;//物品数量、背包容积
for(int i=1; i<=n; i++)
{
cin>>v[i]>>w[i];//物品的体积和价值
}
//f[0][0]=0; //初始化为0
for(int i=1; i<=n; i++) //物品数量
{
for(int j=1; j<=m; j++) //背包容量
{
if(j<v[i]) //第i个物品装不下
{
//第i个背包的容量为j，第i-1个背包的容量也为j
f[i][j]=f[i-1][j];
}
else //第i个物品可以装下
{
//1、上一个单元格的值j
//2、当前商品的价值（j-v[i]）+剩余空间的价值w[i]
//1、2、中取较大的一个，为当前第i个背包的总价值
f[i][j]=max(f[i-1][j], f[i-1][j-v[i]] + w[i]);
//不要忘记加 第i个物品的价值 w[i]
}
}
}
cout<<f[n][m]<<endl;
return 0;
}
2、完全背包问题
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000 0<vi,wi≤1000
输入样例
4 5 1 2 2 4 3 4 4 5
输出样例：
10
公式：
代码：