人工智能基础-动态规划
人工智能基础-动态规划
动态规划与运筹学
田忌赛马中，使用下等马对战上等马，使用上等马和中等马对战中等马和下等马，这就是运筹学的一个应用
运筹学是应用数学的一个分支，用来解决决策问题，使用数学的方法来做出最佳安排，它在博弈论中也占据着重要地位
动态规划是运筹学的一个分支，是计算最佳决策的过程，它的主要思想是“分解”和“记忆”，分解，即把一个问题分为多个相似的子问题；记忆，即保存已经计算出的结果，防止重复计算
适用条件
最优性原理
若当前问题的决策是最优决策，那么子问题的决策也必须是最优决策
无后效性原理
子问题的决策无法直接影响父问题的决策。无论子问题的决策是否是最佳决策，都不会影响到父问题的决策，但是如果子问题的决策不是最佳决策，那么父问题的决策也一定不是最佳决策
重叠性原理
父问题可以分解成多个子问题，而子问题同样也可以分解成多个子问题，这些子问题可能会出现重复，为了减少计算次数，需要在计算后保存子问题的解，在下次遇到时就可以直接使用
斐波那契数列
问题描述
求出前两项都为1的斐波那契数列的第50项
问题分解
用f(n)来表示第n个斐波那契数，则f(n)=f(n-1)+f(n-2)，且当n=1,2时,f(n)=1
代码实现
#include <iostream>
#include <stdio.h>
#include <string.h>
long long fib[51]{};
long long Fibonacci(int i);
int main(){
//打印第50个斐波那契数
printf("%lld\n", Fibonacci(50));
return 0;
}
//返回第i个斐波那契数列的数
long long Fibonacci(int i){
if(fib[i] != 0) return fib[i];
if(i <= 2){
fib[i] = 1;
} else{
fib[i] = Fibonacci(i-1) + Fibonacci(i-2);
}
return fib[i];
}数塔问题
问题描述
Description 设有一个三角形的数塔，顶点结点为根结点，每个结点有一个整数数值。从顶点出发，在每一个结点可以选择向左下走或者向右下走，一直走到底层，要求找出一条路径，使得路径上的和最大。 Input 输入数塔层数n 输入n层数塔 Output 输出最大和 Sample Input 5 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11 Sample Output max=86
问题分解
设第i层，第j个数为a[i][j], 向下走的最大和为f(i, j)，则f(i, j)=a[i, j] + max{f(i+1,j),f(i+1,j+1)}
代码实现
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int n;
int **arr;//由于不知道n的范围，采用指针方式定义
int **res;//储存已经计算过的结果
int f(int i, int j);
int main() {
cin >> n;//输入层数
arr = new int *[n];
res = new int *[n];
for(int i=0;i<n;i++){
arr[i] = new int [n];
res[i] = new int [n]{};//在定义指针的同时初始化数组为0
}
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
cin >> arr[i][j];//输入数字
}
}
cout << "max=" << f(0,0);
return 0;
}
int f(int i, int j){
if(res[i][j] != 0) return res[i][j];
if(i >= n-1){//已经到达最底层
res[i][j] = arr[i][j];
}else{
res[i][j] = arr[i][j] + max(f(i+1,j),f(i+1,j+1));;
}
return res[i][j];
}最长公共子序列
问题描述
Description 给定两个字符串，输出两个字符串的最长公共子序列长度 Input 输入2个字符串(保证字符串长度不超过500) 文件有多组数据以‘#’号结束 Output 输出最长公共子序列长度 Sample Input abc abc abcd acdef # Sample Output 3 3
问题分解
设函数f(i,j)返回字符串a的第i个字符开始，字符串b的第j个字符开始的最长公共序列长度。当i==j时，f(i,j)=f(i-1,j-1)+1，否则,f(i,j)=max{f(i,j-1),f(i-1,j)}
代码实现
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
char a[501];//序列A
char b[501];//序列B
int len_a,len_b;
int res[501][501];
int f(int i, int j);
int main() {
while (cin >> a && a[0] != '#' && cin >> b) {
//初始化res数组
for (int i = 0; i < 501; i++) {
for (int j = 0; j < 501; j++) {
res[i][j] = -1;
}
}
len_a = strlen(a);
len_b = strlen(b);
cout << f(0,0) << endl;
}
return 0;
}
int f(int i, int j) {
if(i >= len_a || j >= len_b) return 0;
if (res[i][j] != -1) return res[i][j];
if (a[i] == b[j]) {
res[i][j] = f(i + 1, j + 1) + 1;
} else {
res[i][j] = max(f(i + 1, j), f(i, j + 1));
}
return res[i][j];
}01背包
导弹拦截问题
问题描述
Description 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数)，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 Input 输入多个数据m：(m<=30000) 389 207 155 300 299 170 158 65 Output 6(最多能拦截的导弹数) 2(要拦截所有导弹最少要配备的系统数) Sample Input 389 207 155 300 299 170 158 65 Sample Output 6 2
问题分解
拦截弹一次比一次低，说明每次导弹的高度会越来越低，把拦截的导弹按序号排序，它们的高度会是一个下降序列，所以最多能拦截的导弹数就是最长下降子序列的长度
同理，每次计算出最长下降子序列之后，移除这条子序列，重复计算，所以最少配备的系统数就是下降子序列的数量，显然，下降子序列的数量就是最长上升子序列的长度，因为在上升子序列里，每一项都一定分布在不同的下降序列里
设导弹数量为len, f(i)表示从i开始的最长下降子序列长度，只需要从它后面的导弹里找出导弹j，使得height(i) >= height(j)，且f(j)+1>=f(i)，则f(i)的值就是f(j)+1
g(i)表示从i开始的最长上升子序列长度，它与f(i)同理，只是要把条件改成height(i) < height(j)
代码实现
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <sstream>
#include <string>
using namespace std;
int temp;
int height[1000];
int len = 0;
int res_f[1000]{};
int res_g[1000]{};
int f(int i);//最长下降子序列
int g(int i);//最长上升子序列
int max_f = 1, max_g = 1;//记录最大值
int main() {
string s;
getline(cin, s);
istringstream istr(s);
//读取导弹高度
while (istr >> temp) {
height[len] = temp;
len++;
}
//求最大值
for (int i = 0; i < len; i++) {
if (f(i) > max_f) max_f = f(i);
if (g(i) > max_g) max_g = g(i);
}
cout << max_f << endl << max_g << endl;
return 0;
}
int f(int i) {
if (res_f[i] != 0) return res_f[i];
res_f[i] = 1;//因为它自己就是一个序列，所以初始值为最小值为1
if (i < len - 1) {
for (int j = i + 1; j < len; j++) {
if (height[i] >= height[j] && f(j) + 1 >= res_f[i]) res_f[i] = f(j) + 1;
}
}
return res_f[i];
}
int g(int i) {
if (res_g[i] != 0) return res_g[i];
res_g[i] = 1;//因为它自己就是一个序列，所以初始值为最小值为1
if (i < len - 1) {
for (int j = i + 1; j < len; j++) {
if (height[i] < height[j] && g(j) + 1 >= res_g[i]) res_g[i] = g(j) + 1;
}
}
return res_g[i];
}