1.貪心算法
基本概念
所謂貪心算法是指，在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。
貪心算法沒有固定的算法框架，算法設(shè)計的關(guān)鍵是貪心策略的選擇。必須注意的是，貪心算法不是對所有問題都能得到整體最優(yōu)解，選擇的貪心策略必須具備無后效性，即某個狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。
所以對所采用的貪心策略一定要仔細(xì)分析其是否滿足無后效性。
貪心算法的基本思路：
1.建立數(shù)學(xué)模型來描述問題。
2.把求解的問題分成若干個子問題。
3.對每一子問題求解，得到子問題的局部最優(yōu)解。
4.把子問題的解局部最優(yōu)解合成原來解問題的一個解。
貪心算法適用的問題
貪心策略適用的前提是：局部最優(yōu)策略能導(dǎo)致產(chǎn)生全局最優(yōu)解。
實(shí)際上，貪心算法適用的情況很少。一般，對一個問題分析是否適用于貪心算法，可以先選擇該問題下的幾個實(shí)際數(shù)據(jù)進(jìn)行分析，就可做出判斷。
貪心算法的實(shí)現(xiàn)框架
從問題的某一初始解出發(fā)；
while (能朝給定總目標(biāo)前進(jìn)一步){
利用可行的決策，求出可行解的一個解元素; }
由所有解元素組合成問題的一個可行解；
貪心策略的選擇
0到1背包問題
有一個背包，背包容量是M=150kg。有7個物品，物品不可以分割成任意大小。要求盡可能讓裝入背包中的物品總價值最大，但不能超過總?cè)萘俊?br>
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
價值 10 40 30 50 35 40 30
分析：
目標(biāo)函數(shù)：∑pi最大
約束條件是裝入的物品總重量不超過背包容量：∑wi<=M(M=150）
⑴根據(jù)貪心的策略，每次挑選價值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？
⑵每次挑選所占重量最小的物品裝入是否能得到最優(yōu)解？
⑶每次選取單位重量價值最大的物品，成為解本題的策略。
但（3）并不是最優(yōu)解，最優(yōu)解應(yīng)用動態(tài)規(guī)劃解題，此處只是示范了一下貪心算法的思考過程
例題：
問題描述
已知一個正整數(shù)N，問從1~N中任選出三個數(shù)，他們的最小公倍數(shù)最大可以為多少。
輸入格式
輸入一個正整數(shù)N。
輸出格式
輸出一個整數(shù)，表示你找到的最小公倍數(shù)。
樣例輸入
9
樣例輸出
504
數(shù)據(jù)規(guī)模與約定
1 <= N <= 106。
思考：
①必定是要找最后的幾位數(shù)字，所以猜測為最后三位。
當(dāng)n為奇數(shù)，n,n-1,n-2中必定沒有2作為公因子，也不會有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)：
有一個文本串S，和一個模式串P，查找P在S中的位置
首先想到的是，將P一個個的與S比較，遇到不匹配的字符，就從下一個位置繼續(xù)比較（暴力）
它有個洋氣的名字叫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是夢開始的地方，i-j+1就是從跌倒的地方往前邁一步，達(dá)到每每比較的目的
j=0;}
}
if(j==plen){
return i-j+1;
}else{
return -1;}
}
為了解決暴力解決速度太慢的算法改進(jìn)（暴力的時間復(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ù)匹配下一個字符；
<2>如果j != -1，且當(dāng)前字符匹配失?。碨[i] != P[j]），則令 i 不變，j = next[j]。此舉意味著失配時，模式串P相對于文本串S向右移動了j - next [j] 位。
換言之，當(dāng)匹配失敗時，模式串向右移動的位數(shù)為：失配字符所在位置 - 失配字符對應(yīng)的next 值，即移動的實(shí)際位數(shù)為：j - next[j]，且此值大于等于1。
next 數(shù)組各值的含義：代表當(dāng)前字符之前的字符串中，有多大長度的相同前綴后綴。例如如果next [j] = k，代表j 之前的字符串中有最大長度為k 的相同前綴后綴。
此也意味著在某個字符失配時，該字符對應(yīng)的next 值會告訴你下一步匹配中，模式串應(yīng)該跳到哪個位置（跳到next [j] 的位置）。如果next [j] 等于0或-1，則跳到模式串的開頭字符，若next [j] = k 且 k > 0，代表下次匹配跳到j(luò) 之前的某個字符，而不是跳到開頭，且具體跳過了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(chǎn)和后置的a，也是加一，1
j=7,前置的ab（1和2號）和后置的ab（5和6號位）....
得到上表
實(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所對應(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模式串在主串中的序號：");
printf("%d\n", index);
}
else {
printf("\n\n在主串中未找到模式串\n");
}
return 0;
}
