1.貪心算法
基本概念
所謂貪心算法是指乌企，在對(duì)問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇成玫。也就是說加酵，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解梁剔。
貪心算法沒有固定的算法框架虽画，算法設(shè)計(jì)的關(guān)鍵是貪心策略的選擇。必須注意的是荣病，貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解码撰，選擇的貪心策略必須具備無后效性，即某個(gè)狀態(tài)以后的過程不會(huì)影響以前的狀態(tài)个盆，只與當(dāng)前狀態(tài)有關(guān)脖岛。
所以對(duì)所采用的貪心策略一定要仔細(xì)分析其是否滿足無后效性。
貪心算法的基本思路：
1.建立數(shù)學(xué)模型來描述問題颊亮。
2.把求解的問題分成若干個(gè)子問題柴梆。
3.對(duì)每一子問題求解，得到子問題的局部最優(yōu)解终惑。
4.把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解绍在。
貪心算法適用的問題
貪心策略適用的前提是：局部最優(yōu)策略能導(dǎo)致產(chǎn)生全局最優(yōu)解。
實(shí)際上雹有，貪心算法適用的情況很少偿渡。一般，對(duì)一個(gè)問題分析是否適用于貪心算法霸奕，可以先選擇該問題下的幾個(gè)實(shí)際數(shù)據(jù)進(jìn)行分析溜宽，就可做出判斷。
貪心算法的實(shí)現(xiàn)框架
從問題的某一初始解出發(fā)质帅；
while (能朝給定總目標(biāo)前進(jìn)一步){
利用可行的決策适揉，求出可行解的一個(gè)解元素; }
由所有解元素組合成問題的一個(gè)可行解留攒；
貪心策略的選擇
0到1背包問題
有一個(gè)背包，背包容量是M=150kg嫉嘀。有7個(gè)物品炼邀，物品不可以分割成任意大小。要求盡可能讓裝入背包中的物品總價(jià)值最大剪侮，但不能超過總?cè)萘俊?br>
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
價(jià)值 10 40 30 50 35 40 30
分析：
目標(biāo)函數(shù)：∑pi最大
約束條件是裝入的物品總重量不超過背包容量：∑wi<=M(M=150）
⑴根據(jù)貪心的策略汤善，每次挑選價(jià)值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)票彪？
⑵每次挑選所占重量最小的物品裝入是否能得到最優(yōu)解红淡？
⑶每次選取單位重量價(jià)值最大的物品，成為解本題的策略降铸。
但（3）并不是最優(yōu)解在旱，最優(yōu)解應(yīng)用動(dòng)態(tài)規(guī)劃解題，此處只是示范了一下貪心算法的思考過程
例題：
問題描述
已知一個(gè)正整數(shù)N推掸，問從1~N中任選出三個(gè)數(shù)桶蝎，他們的最小公倍數(shù)最大可以為多少。
輸入格式
輸入一個(gè)正整數(shù)N谅畅。
輸出格式
輸出一個(gè)整數(shù)登渣，表示你找到的最小公倍數(shù)。
樣例輸入
9
樣例輸出
504
數(shù)據(jù)規(guī)模與約定
1 <= N <= 106毡泻。
思考：
①必定是要找最后的幾位數(shù)字胜茧，所以猜測(cè)為最后三位。
當(dāng)n為奇數(shù)仇味，n,n-1,n-2中必定沒有2作為公因子呻顽，也不會(huì)有3（因?yàn)樽畲笙嗖钪挥?）
所以當(dāng)n為奇數(shù)，最大最小公倍數(shù)=n(n-1)(n-2)
②當(dāng)n為偶數(shù)丹墨，因?yàn)閚與n-2有公因子2廊遍，所以不能選，于是改成n-3
但是如果n和n-3之間有公因子3贩挣，那更得不償失了喉前，所以需要判斷一下。如果n能被3整除王财，就把三位全部往后移一位卵迂，變成了情況1全為奇數(shù)的樣子~
<1>如果n能被3整除，最小公倍數(shù)=(n-1)(n-2)(n-3)
<2>如果n不能被3整除搪搏，最小公倍數(shù)=n(n-1)(n-3)
//實(shí)現(xiàn)代碼
#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算法
出現(xiàn)的原因
問題目標(biāo)：
有一個(gè)文本串S狭握，和一個(gè)模式串P闪金，查找P在S中的位置
首先想到的是疯溺，將P一個(gè)個(gè)的與S比較论颅，遇到不匹配的字符，就從下一個(gè)位置繼續(xù)比較（暴力）
它有個(gè)洋氣的名字叫BF算法（劃掉）
//暴力實(shí)現(xiàn)函數(shù)
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是夢(mèng)開始的地方囱嫩，i-j+1就是從跌倒的地方往前邁一步恃疯，達(dá)到每每比較的目的
j=0;}
}
if(j==plen){
return i-j+1;
}else{
return -1;}
}
為了解決暴力解決速度太慢的算法改進(jìn)（暴力的時(shí)間復(fù)雜度是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;
}
}
其實(shí)這樣看起來今妄，除了while循環(huán)里的else稍有區(qū)別之外，其他與BF區(qū)別不大鸳碧，所以我們接下來的任務(wù)是實(shí)現(xiàn)next[j]
什么是next[j]:
假設(shè)現(xiàn)在文本串S匹配到 i 位置盾鳞，模式串P匹配到 j 位置
<1>如果j = -1，或者當(dāng)前字符匹配成功（即S[i] == P[j]）瞻离，都令i++腾仅，j++，繼續(xù)匹配下一個(gè)字符套利；
<2>如果j != -1推励，且當(dāng)前字符匹配失敗（即S[i] != P[j]）肉迫，則令 i 不變验辞，j = next[j]。此舉意味著失配時(shí)喊衫，模式串P相對(duì)于文本串S向右移動(dòng)了j - next [j] 位跌造。
換言之，當(dāng)匹配失敗時(shí)族购，模式串向右移動(dòng)的位數(shù)為：失配字符所在位置 - 失配字符對(duì)應(yīng)的next 值鼻听，即移動(dòng)的實(shí)際位數(shù)為：j - next[j]，且此值大于等于1联四。
next 數(shù)組各值的含義：代表當(dāng)前字符之前的字符串中撑碴，有多大長度的相同前綴后綴。例如如果next [j] = k朝墩，代表j 之前的字符串中有最大長度為k 的相同前綴后綴醉拓。
此也意味著在某個(gè)字符失配時(shí)，該字符對(duì)應(yīng)的next 值會(huì)告訴你下一步匹配中收苏，模式串應(yīng)該跳到哪個(gè)位置（跳到next [j] 的位置）亿卤。如果next [j] 等于0或-1，則跳到模式串的開頭字符鹿霸，若next [j] = k 且 k > 0排吴，代表下次匹配跳到j(luò) 之前的某個(gè)字符，而不是跳到開頭懦鼠，且具體跳過了k 個(gè)字符钻哩。
舉個(gè)例子：
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時(shí)，next為-1（初始）
j=2街氢，b之前沒有前置字符串（從1號(hào)位開始）和后置字符串（從j-1往前）扯键，無法比較，即為0
j=3珊肃，依舊沒有.....j=5,1號(hào)位的a和4號(hào)位的a相同荣刑，加一，next為1
j=6,前置字符串a(chǎn)和后置的a伦乔，也是加一厉亏，1
j=7,前置的ab（1和2號(hào)）和后置的ab（5和6號(hào)位）....
得到上表
實(shí)現(xiàn)代碼
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，或者當(dāng)前字符匹配成功（即S[i] == P[j]）烈和，都令i++叶堆，j++
if (j == -1 || s[i] == p[j]){
i++;
j++;
}else{
//②如果j != -1，且當(dāng)前字符匹配失敵舛拧（即S[i] != P[j]）虱颗，則令 i 不變，j = next[j]
//next[j]即為j所對(duì)應(yīng)的next值
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
}
算法改進(jìn)
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
實(shí)現(xiàn)代碼
#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];
}
}
//顯示函數(shù)
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模式串在主串中的序號(hào)：");
printf("%d\n", index);
}
else {
printf("\n\n在主串中未找到模式串\n");
}
return 0;
}
