用蛮力法解决01背包问题及KMP算法

云间鱼

      任务要求：
1.应用蛮力法解决0/1背包问题 ；
对所设计的算法进行时间复杂性分析；

2. 给定一个文本，在该文本中查找并定位
任意给定字符串，实现BF算法或BF算法
的改进算法KMP算法。；








01背包问题需要列举出所有可能来意义检查，确定方案。确定其中重量小于要求的背包重量，在剩下的情况中来选择价值最大的情况。
1.设计方案：
用4二进制方法x4x3x2x1表示选择，x1为1表示选择第一个，为0 表示不选择,其他以此类推。第一个0-16，与1相与，来对第一个货物选择；与2相与对第二个货物选择；与4相与对第三个货物选择；与8相与，对第四个货物选择。
2.源代码：
#include<stdio.h>
#include<math.h>
#define SIZE 4
int deal(int i);
struct woods{
        int value;
        int weight;
        woods(int w,int v){
                this->value=v;
                this->weight=w;
        }
};
    woods woods1(7,42);
        woods woods2(3,12);
        woods woods3(4,40);
        woods woods4(5,25);
int main(){
        //int count=15;
        int max=0;
       
        for(int i=0;i<(pow(2,SIZE));i++){
       
                if(max<deal(i)){
               
                max=deal(i);}
        }
        printf("\n最大价值是：%d",max);
/*        if(count&1){
                printf("dsf");
        }*/
        return 0;
}
int deal(int i){
        int weig=0;
        int value1=0;
        if(i&1){
               
                weig=woods1.weight+weig;
                value1=woods1.value+value1;       
                }
                if(i&2){
                weig=woods2.weight+weig;
                value1=woods2.value+value1;               
                }
                if(i&4){
                        weig=woods3.weight+weig;
                        value1=woods3.value+value1;       
                }
                if(i&8){
                        weig=woods4.weight+weig;
                        value1=woods4.value+value1;       
                }
        if(weig<11){
                if(i&1)
                {printf("选择货物1,");}
                if(i&2)
                {printf("选择货物2,");}
                if(i&4)
                {printf("选择货物3,");}
                if(i&8)
                {printf("选择货物4,");}
                //printf("第%d种方案\n",i);
                printf("总价值是%d\n",value1);
                return value1;
        }
        return 0;
}
使用i为1-16与1，2，4，8相与来选择4种方案，并且确定其中总重量小于背包要求重量的总价值最大的选择情况。时间复杂度是O（n);


kmp算法完成的任务是：给定两个字符串S和T，长度分别为n和m，判断T是否在S中出现，如果出现则返回出现的位置。
1.设计方案：
kmp算法的核心即是计算字符串T每一个位置之前的字符串的前缀和后缀公共部分的最大长度。获得T每一个位置的最大公共长度之后，就可以利用该最大公共长度快速和字符串S比较。当每次比较到两个字符串的字符不同时，我们就可以根据最大公共长度将字符串T向前移动(已匹配长度-最大公共长度)位，接着继续比较下一个位置。只要我们在比较的时候从最大公共长度之后比较T和S即可达到字符串T前移的目的。

2.算法：采用KMP算法。
3.源代码：

1. #include<stdio.h>
   
2. #include<math.h>
   
3. #define SIZE 4
   
4. int deal(int i);
   
5. struct woods{
   
6.         int value;
   
7.         int weight;
   
8.         woods(int w,int v){
   
9.                 this->value=v;
   
10.                 this->weight=w;
    
11.         }
    
12. };
    
13.     woods woods1(7,42);
    
14.         woods woods2(3,12);
    
15.         woods woods3(4,40);
    
16.         woods woods4(5,25);
    
17. int main(){
    
18.         //int count=15;
    
19.         int max=0;
    
20.        
    
21.         for(int i=0;i<(pow(2,SIZE));i++){
    
22.        
    
23.                 if(max<deal(i)){
    
24.                
    
25.                 max=deal(i);}
    
26.         }
    
27.         printf("\n最大价值是：%d",max);
    
28. /*        if(count&1){
    
29.                 printf("dsf");
    
30.         }*/
    
31.         return 0;
    
32. }
    
33. int deal(int i){
    
34.         int weig=0;
    
35.         int value1=0;
    
36.         if(i&1){
    
37.                
    
38.                 weig=woods1.weight+weig;
    
39.                 value1=woods1.value+value1;       
    
40.                 }
    
41.                 if(i&2){
    
42.                 weig=woods2.weight+weig;
    
43.                 value1=woods2.value+value1;               
    
44.                 }
    
45.                 if(i&4){
    
46.                         weig=woods3.weight+weig;
    
47.                         value1=woods3.value+value1;       
    
48.                 }
    
49.                 if(i&8){
    
50.                         weig=woods4.weight+weig;
    
51.                         value1=woods4.value+value1;       
    
52.                 }
    
53.         if(weig<11){
    
54.                 if(i&1)
    
55.                 {printf("选择货物1,");}
    
56.                 if(i&2)
    
57.                 {printf("选择货物2,");}
    
58.                 if(i&4)
    
59.                 {printf("选择货物3,");}
    
60.                 if(i&8)
    
61.                 {printf("选择货物4,");}
    
62.                 //printf("第%d种方案\n",i);
    
63.                 printf("总价值是%d\n",value1);
    
64.                 return value1;
    
65.         }
    
66.         return 0;
    
67. }
    
68. 
    
69. 
    
70. 
    
71. /*KMP*/
    
72. #include"stdio.h"
    
73. #include"string.h"
    
74. #include"time.h"
    
75. 
    
76.         int Next[20];
    
77.         void get_next(char *T,int next[]){
    
78.                 int i=0;next[i]=-1;
    
79.                 int j=-1;
    
80.                 int m=strlen(T);
    
81.                 while(i<m){
    
82.                         if(j==-1||T[i]==T[j]){
    
83.                                 ++i;++j;
    
84.                                 next[i]=j;
    
85.                         }
    
86.                         else j=next[j];
    
87.                 }
    
88.         }
    
89. int Index_KMP(char *S,char *T,int pos){
    
90.          
    
91. 
    
92.     int i = 0;  
    
93.     int j = 0;  
    
94.     int sLen = strlen(S);  
    
95.     int pLen = strlen(T);  
    
96.     while (i < sLen && j < pLen)  
    
97.     {  
    
98.            
    
99.         if (j == -1 || S[i] == T[j])  
    
100.         {  
     
101.             i++;  
     
102.             j++;  
     
103.         }  
     
104.         else  
     
105.         {  
     
106.                
     
107.             j = Next[j];  
     
108.         }  
     
109.     }  
     
110.     if (j == pLen)  
     
111.         return i - j;  
     
112.     else  
     
113.         return -1;  
     
114. 
     
115.        
     
116. }
     
117. int main(){
     
118.         char S[]="fdfopgkpoieweuvnsalapytjerj";
     
119.         char T[]="kpoiewe";
     
120.          get_next(T,Next);
     
121.          int pos;//第一次匹配的位置
     
122.          int repeats=10000000;
     
123.          printf("需要匹配的字符串是%s和%s\n",S,T);
     
124.          time_t tBegin,tEnd;
     
125.          time(&tBegin);
     
126.          for(int i=0;i<repeats;i++)
     
127.          pos=Index_KMP(S,T,0);
     
128.          time(&tEnd);
     
129.          float cost=tEnd-tBegin;
     
130.          printf("使用KMP，匹配的位置是：%d,耗时%.2fs\n",pos,cost);
     
131.        
     
132.          return 0;
     
133.           }

复制代码

实验结果见图片。

第一次发帖，有什么做的不好的，欢迎私我指正。