1.贪心算法
基本概念
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
贪心算法的基本思路：
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
贪心算法适用的问题
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。
贪心算法的实现框架
从问题的某一初始解出发；
while (能朝给定总目标前进一步){
利用可行的决策，求出可行解的一个解元素; }
由所有解元素组合成问题的一个可行解；
贪心策略的选择
0到1背包问题
有一个背包，背包容量是M=150kg。有7个物品，物品不可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
价值 10 40 30 50 35 40 30
分析：
目标函数：∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M(M=150）
⑴根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
⑵每次挑选所占重量最小的物品装入是否能得到最优解？
⑶每次选取单位重量价值最大的物品，成为解本题的策略。
但（3）并不是最优解，最优解应用动态规划解题，此处只是示范了一下贪心算法的思考过程
例题：
问题描述
已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。
输入格式
输入一个正整数N。
输出格式
输出一个整数，表示你找到的最小公倍数。
样例输入
9
样例输出
504
数据规模与约定
1 <= N <= 106。
思考：
①必定是要找最后的几位数字，所以猜测为最后三位。
当n为奇数，n,n-1,n-2中必定没有2作为公因子，也不会有3（因为最大相差只有2）
所以当n为奇数，最大最小公倍数=n(n-1)(n-2)
②当n为偶数，因为n与n-2有公因子2，所以不能选，于是改成n-3
但是如果n和n-3之间有公因子3，那更得不偿失了，所以需要判断一下。如果n能被3整除，就把三位全部往后移一位，变成了情况1全为奇数的样子~
<1>如果n能被3整除，最小公倍数=(n-1)(n-2)(n-3)
<2>如果n不能被3整除，最小公倍数=n(n-1)(n-3)
//实现代码
#include<iostream>
using namespace std;
int main(){
long long int sum,n;
cin>>n;
if(n<=2){
sum=n;
}else if(n%2==1){
sum=(n)*(n-1)*(n-2);
}else{
if(n%3==0)
sum=(n-1)*(n-2)*(n-3);
else
sum=n*(n-1)*(n-3);
}
cout<<sum<<endl;
return 0;
}
2.KMP算法
出现的原因
问题目标：
有一个文本串S，和一个模式串P，查找P在S中的位置
首先想到的是，将P一个个的与S比较，遇到不匹配的字符，就从下一个位置继续比较（暴力）
它有个洋气的名字叫BF算法（划掉）
//暴力实现函数
int baoli(char *s,char *p){
int slen=strlen(s);
int plen=strlen(p);
int i=0,j=0;
while(i<slen&&j<plen){
if(s[i]==p[j]){
i++;j++;
}else{
i=i-j+1;//i-j是梦开始的地方，i-j+1就是从跌倒的地方往前迈一步，达到每每比较的目的
j=0;}
}
if(j==plen){
return i-j+1;
}else{
return -1;}
}
为了解决暴力解决速度太慢的算法改进（暴力的时间复杂度是O(N * M)），可大大提升速度，为O（N * M）
算法描述
先看一下KMP的整体框架
int Index_KMP(HString S, HString T, int pos, int next[]) {
int i = pos - 1;
int j = 0;
while (i < S.length&&j < T.length) {
if (j ==-1||S.ch[i] == T.ch[j]) {
++i; ++j;
}else {
j = next[j];//此处不同
}
}
if (j >= T.length) {
return i - T.length + 1;
}else {
return 0;
}
}
其实这样看起来，除了while循环里的else稍有区别之外，其他与BF区别不大，所以我们接下来的任务是实现next[j]
什么是next[j]:
假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
<1>如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
<2>如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。
换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值，即移动的实际位数为：j - next[j]，且此值大于等于1。
next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀。
此也意味着在某个字符失配时，该字符对应的next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置）。如果next [j] 等于0或-1，则跳到模式串的开头字符，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，而不是跳到开头，且具体跳过了k 个字符。
举个例子：
j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
模式串 a b c a a b b c a b c a a b d a b
next[j] -1 0 0 0 1 1 2 0 0 1 2 3 4 5 6 0 1
首先，j=1时，next为-1（初始）
j=2，b之前没有前置字符串（从1号位开始）和后置字符串（从j-1往前），无法比较，即为0
j=3，依旧没有.....j=5,1号位的a和4号位的a相同，加一，next为1
j=6,前置字符串a和后置的a，也是加一，1
j=7,前置的ab（1和2号）和后置的ab（5和6号位）....
得到上表
实现代码
int KmpSearch(char* s, char* p){
int i = 0;
int j = 0;
int sLen = strlen(s);
int pLen = strlen(p);
while (i < sLen && j < pLen){
//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
if (j == -1 || s[i] == p[j]){
i++;
j++;
}else{
//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
//next[j]即为j所对应的next值
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
}
算法改进
j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
模式串 a b c a a b b c a b c a a b d a b
next[j] -1 0 0 0 1 1 2 0 0 1 2 3 4 5 6 0 1
nextval[j]-1 0 0 -1 1 0 2 0 -1 0 0 -1 1 0 6 -1 0
实现代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct {
char *ch;
int length;
}HString;
//将输入的字符串放入
void StrAssign(HString &T, char *s) {
int i;
T.length = strlen(s);
T.ch = (char *)malloc(T.length * sizeof(char));
for (i = 0; i < T.length; i++) {
T.ch[i] = s[i];
}
}
//显示函数
void Print(HString T) {
int i;
for (i = 0; i < T.length; i++) {
printf("%c ", T.ch[i]);
}
printf("\n");
}
//
void get_nextval(HString T, int nextval[]) {
int i = 0;
nextval[0] = -1;
int j = -1;
while (i < T.length - 1) {
if (j == -1 || T.ch[i] == T.ch[j]) {
++i; ++j;
if (T.ch[i] != T.ch[j]) {
nextval[i] = j;
}
else {
nextval[i] = nextval[j];
}
}
else {
j = nextval[j];
}
}
}
int Index_KMP(HString S, HString T, int pos, int next[]) {
int i = pos - 1;
int j = 0;
while (i < S.length&&j < T.length) {
if (j ==-1||S.ch[i] == T.ch[j]) {
++i; ++j;
}
else {
j = next[j];
}
}
if (j >= T.length) {
return i - T.length + 1;
}
else {
return 0;
}
}
int main() {
HString t, p;
int i, index = 0;
char a[] = "aabcbabcaabcaababc";
char b[] = "abcaaba";
StrAssign(t, a);
printf("主串：\n\t");
Print(t);
StrAssign(p, b);
printf("模式串：\n\t");
Print(p);
int *next = (int *)malloc(p.length * sizeof(int));
get_nextval(p, next);
printf("模式串的next值：\n\t");
for (i = 0; i < p.length; i++) {
printf("%d ", next[i]);
}
index = Index_KMP(t, p, 1, next);
if (index) {
printf("\n\n模式串在主串中的序号：");
printf("%d\n", index);
}
else {
printf("\n\n在主串中未找到模式串\n");
}
return 0;
}
