用蛮力法解决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.源代码：

#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;
}



/*KMP*/
#include"stdio.h"
#include"string.h"
#include"time.h"
 
        int Next[20];
        void get_next(char *T,int next[]){
                int i=0;next[i]=-1;
                int j=-1;
                int m=strlen(T);
                while(i<m){
                        if(j==-1||T[i]==T[j]){
                                ++i;++j;
                                next[i]=j;
                        }
                        else j=next[j];
                }
        }
 int Index_KMP(char *S,char *T,int pos){
          

    int i = 0;  
    int j = 0;  
    int sLen = strlen(S);  
    int pLen = strlen(T);  
    while (i < sLen && j < pLen)  
    {  
           
        if (j == -1 || S[i] == T[j])  
        {  
            i++;  
            j++;  
        }  
        else  
        {  
               
            j = Next[j];  
        }  
    }  
    if (j == pLen)  
        return i - j;  
    else  
        return -1;  

         
 }
 int main(){
         char S[]="fdfopgkpoieweuvnsalapytjerj";
         char T[]="kpoiewe";
         get_next(T,Next);
         int pos;//第一次匹配的位置 
         int repeats=10000000;
         printf("需要匹配的字符串是%s和%s\n",S,T);
         time_t tBegin,tEnd;
         time(&tBegin);
         for(int i=0;i<repeats;i++)
         pos=Index_KMP(S,T,0);
         time(&tEnd);
         float cost=tEnd-tBegin;
         printf("使用KMP，匹配的位置是：%d,耗时%.2fs\n",pos,cost);
        
         return 0;
          }

实验结果见图片。

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