第五讲——动态规划

文章目录

• 一、算法图解
• • 1、背包问题
  • • 1.1 最近红红买了个新背包，但是这个新背包的容量只有4磅，装入什么可使背包中物品的价值最大
    • 1.2 背包问题Q&A
    • • 1.2.1 再增加一件可选商品如何呢？
      • 1.2.2 行的排列顺序 发生变化时结果将如何
      • 1.2.3 旅游行程最优化
      • 1.2.4 处理相互依赖的情况
  • 2、最长公共子串
  • • • 2.1 找出单词hish和fish的最长公共子串
  • 3、最长公共子序列
  • • 3.1 假设红红不小心输入了fosh，他原本想输入的是fish还是fort呢？
• 二、题目/代码
• • 1、背包问题
  • 2、完全背包问题

一、算法图解 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

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

公式：

if(j 
AC代码：
 
#include
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 
2、完全背包问题 
 
 
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
 
 
第 i 种物品的体积是 vi，价值是 wi。
 
 
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。
 
 
输入格式
 
 
 
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
 
 
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。
 
 
输出格式
 
 
 
输出一个整数，表示最大价值。
 
 
数据范围
 
 
 
0 
 
输入样例
 
 
 
4 5 1 2 2 4 3 4 4 5
 
 
输出样例：
 
 
 
10
 
 
公式：
 
代码：