Gallifrey的计算机学习日记

动态规划简介Dynamic Programming 动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。 多阶段决策问题 是动态决策问题的一种特殊形式； 在多阶段决策过程中,系统的动态过程可以按照时间进程分为状态相互联系而又相互区别的各个阶段； 在多阶段决策过程中,系统的动态过程可以按照时间进程分为状态相互联系而又相互区别的各个阶段； 动态规划的基本思想基本概念 阶段： 把一个问题的过程，恰当地分为若干个相互联系的阶段，以便于按一定的次序去求解。 描述阶段的变量称为阶段变量k 。 状态： 表示每个阶段开始所处的条件。 通常一个阶段有若干个状态，描述过程状态的变量称为状态变量s~k~ 。 决策： 当处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策。 描述决策的变量，称为决策变量uk。 多阶段决策过程 其发展是通过一系列的状态转移来实现的； 通常，系统在某一阶段的状态转移不但与系统的当前的状态和决 ...

需求某农户计划种植黄瓜和韭菜，种植面积不超过50亩，投入资金不超过54万元。假设种植黄瓜和韭菜的产量、成本和售价如下表。 为使一年的种植总利润（总利润=总销售收入 —总种植成本）最大，那么黄瓜和韭菜的种植面积（单位：亩）分别为多少？ 年产量/亩 年种植成本/亩 每吨售价 黄瓜 4吨 1.2万元 0.55万元 韭菜 6吨 0.9万元 0.3万元 （1）写出线性规划公式，并转换成标准型 （2）编程解决该问题（matlab代码或者python代码，提交源码附件） 公式原始公式设黄瓜和韭菜的种植面积分别是x1,x2 决策变量：x1,x2 目标函数：max 1 x1+ 10.9 x2 约束条件： x1+x2<=50 1.2 x1 +0.9 x2<=54 x1> 0 ,x2>0 标准化 目标函数：max 1 x1 +0.9 x2 +0 x3 +0 x4 S.T: x1+x2+x3=50 1.2 x1+0.9 x2 +x4=54 x1>0,x2>0,x3>0,x4 代码实现（python）算 ...

线性规划介绍线性规划描述了一大类优化任务，这些任务的共同特点是约束条件和优化准则都可以表示为线性函数。 线性规划所研究的对象属于最优化的范畴，本质上是一个极值问题。三个基本要素： 决策变量：决策者所控制的量，它们的取值由决策者决定 约束条件：决策变量在这些限制范围内才有意义 目标函数：代表决策者希望对其优化的指标。目标函数是决策变量的函数。 示例：利润最大化巧克力作坊生成两种产品：Pyramide和Nuit -假设每天生产x1盒pyramide和x2盒Nuit，前者利润为$1，后者每盒$6 -市场需求，每日最多200盒Pyramide,300盒Nuit -巧克力作坊每日最多生成400盒巧克力 问：如何做到利润最大化 线性规划： -决策变量：x1,x2 -目标函数：max 1x1+6x2 -约束条件：x1<=200 ​ x2<=300 ​ x1+x2<=400 ​ x1>=0&&x2>=0 图解法求解 建 ...

需求 贪心策略解决背包问题或者活动安排问题（二选一），编程实现 dijkstra算法编程实现 或者Prim算法编程实现（二选其一） Kruskal算法编程实现 Huffman编码编程实现（选做） 实现背包问题代码实现测试运行1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192#include<iostream>const int N = 10000;using namespace std;double maxWeight; //最大承受重量double currentWeight; //临时重量double bestValue; //最大价值int n; //物品数量double value[N]; //记录物品价值价值的数组double weight[N] ...

贪心策略基本思想换硬币问题 贪心算法思想 适用问题 活动安排问题 算法实现 这里是代码是不完整的，执行前，编写并执行先一个排序 贪心的基本要素 背包问题 注意：这里是普通背包问题，不是01背包问题 贪心依据的选择 价值优先——次优解 容量优先——次优解 单位利益值——最优解 算法实现 Dijkstra算法 最小生成树 Prim算法 Kruskal算法 解决环的问题 哈夫曼编码 Data Compression via Huffman Coding Motivation Limited network bandwidth. Limited disk space. Human codes are used for data compression. Reducing time to transmit large files, and Reducing the space required to store them on disk or tape. Huffman codes are a widely used ...

需求 百钱白鸡问题，穷举法求解，要求二重循环编程解决。 DFS算法编程实现 0-1背包问题，回溯法编程解决（剪枝函数选做，非必需） 8皇后问题，回溯法编程实现 BFS算法编程实现 实现百钱百鸡问题代码实现测试运行123456789101112#include<iostream>using namespace std;int main() { int a, b; for (a = 1; a <= 20; a++) for (b = 1; b <= 33; b++) { if ((100 - a - b) % 3 == 0&&(5 * a + 3 * b + (100 - a - b) / 3 == 100)) { printf("%d %d %d\n", a, b, 100-a-b); } }} DFS实现代码实现测试运行 这里是利用DFS实现图的遍历，测试图如下 12345678910111213141516171819202122232 ...

搜索法 穷举法 回溯法 分支界限法 穷举策略 不经过思考（很少思考），把问题的所有情况和所有过程交给计算机去一一尝试。 顺序查找 穷举搜索 穷举法解决问题的过程 找出问题的范围 找出约束条件 百钱百鸡问题 我国古代数学家张丘建在《算经》一书中提出的数学问题： 鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各何？ 算法一 求解范围：每种鸡数目<=100约束条件：a+b+c=100 ((5*a)+(3*b)+(c/3))=100 12345for(a=1;a<=100;a++) for(b=1;b<=100;b++) for(b=1;b<=100;b++) if((5*a)+(3*b)+(c/3))==100)and(a+b+c=100 )) printf("%d %d %d\n",a,b,c); 算法效率：尝试1000000次 优化 缩减求解范围 ...

需求 解释分治策略的基本思想，并用它分析大整数相乘问题 选做：编程实现大整数相乘问题（选做） 编程实现二分搜索，快速排序，棋盘覆盖问题 编程实现归并排序，并简述其中的分治策略体现在哪里（选做） 实现大整数相乘解释与分析代码实现测试运行 分治策略思想： 分：把问题分解成两个或者更小规模的子问题 治：利用递归解决子问题 合：归并子问题的解得到原问题的解 如果用分治策略解大整数相乘问题： 把两个整数拆分成四个小整数相乘 利用·AD+BC）=（A+B）*（C+D）-AC-BD替换，将4次乘法运算降低到3次 这里的大整数相乘只是着重于降低算法的时间复杂度，并不能真正做到大整数相乘（溢出） 要写出真正的大整数相乘，应该用一个字符数组来输入输出数组 感兴趣的读者可以参考基础算法二 | Gallifrey’s Blog中高精度乘法，编写真正的两个大整数相乘代码 1234567891011121314151617181920212223242526272829303132333435363738#include <iostream>using namespace s ...

Divide and Conquer分析图 简介 适用条件 算法实现 算法分析 大整数相乘 利用（AD+BC）=（A+B）*（C+D）-AC-BD替换，将4次乘法运算降低到3次 分治策略举例 二分查找 二叉查找树，平衡二叉树，B树和B+树 排序问题 归并排序（Merge Sort） 快速排序 二分查找 归并排序Merge Sort 快速排序 12345678910111213void quicksort(int arr[], int low, int high) { if (low >= high) return;//没有数返回 int l = low, h = high; int x = arr[low]; while (low < high) { while ((low < high) && (arr[high] >= x)) high--; swap(arr[low], arr[high]); while ((low < high) && (arr[low] ...

需求 编程实现斐波那契数列，分别用递归法，数组法。比较实验结果，分析原因。 设计空间复杂度更好的算法，实现斐波那契数列。 编程实现汉诺塔问题 全排列问题（选做） 实现斐波那契数列斐波那契数列--递归法斐波那契数列--数组法比较与分析改进算法--迭代法12345678910111213141516#include<iostream>#include<time.h>using namespace std;int cnt = 0;//统计循环次数int fun1(int n ) { cnt++; if (n == 1) return 1; if (n == 2) return 1; return fun1(n - 1) + fun1(n - 2);}void main() { cout <<"fun1(25): "<< fun1(25) << endl; cout <<"循环次数: " << cnt << endl;
...