用蛮力法解决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;
void get_next(char *T,int next[]){
int i=0;next=-1;
int j=-1;
int m=strlen(T);
while(i<m){
if(j==-1||T==T){
++i;++j;
next=j;
}
else j=next;
}
}
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 == T)
{
i++;
j++;
}
else
{
j = Next;
}
}
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;
}
实验结果见图片。
第一次发帖，有什么做的不好的，欢迎私我指正。{:5_109:}
页:
[1]