上课内容

蛮力法解释

一、蛮力法的概念
也称之为 穷举法【枚举法，暴力破解】
它是算法中最常用的算法之一。
基本思想： 对问题的所有可能状态一一测试【所有的可能一个都不放过！】
直到找到解或者全部可能状态为止
二、蛮力法的优点
1 逻辑清楚，编写程序简洁
2 可以用来解决生活很多问题【应用领域广】
3 对于一些重要的问题，它可以产生一些合理的算法
4 可以解决一些小规模的问题
5 可以作为其他高效算法的衡量的标准
【为何高效？需要对比的对象】
【比如：你说你很帅？！ 武大郎，彭于晏】

三、蛮力法的缺点
1 它所涉及到算法大多数效率低
2 主要解决的问题规模偏小
3 蛮力法的依赖的基本计算机思想：扫描技术。

四、蛮力法通常使用的几种情况
1 搜索所有的解
2 搜索所有的路径【最短路径等问题】
3 直接计算【简单粗暴】
4 模拟和仿真【计算机科学与技术，学matlb】
【深度优先算法和广度优先算法：其实本质上还是算作蛮力法。只是它算作是高级版本的蛮力法】
五、采用蛮力法设计算法的2类：
1 采用基本穷举思想【简单，直接】
2 在穷举思想中融入递归算法【相对复杂】

例1 插入排序

分析：
基本思想：
举例说明：

插入排序的思想：
把某个位置上的的数值，插入到它最合适的位置

考虑第0个数值6，不管其他，它就在这个位置就好了

考虑第1个数值4，由于6>4,所以4插入到6之前

考虑第2个数值7，由于6<7,所以7就站在原位就好了
而4就没必要判断

考虑第3个数值4， 由于7>3，所以3插入到7之前
由于6>3，所以3插入到6之前
由于4>3，所以3插入到4之前
因为3之前没有数据的了所以停止

下面重复

if(a[7]<a[6])
{t=a[7];a[7]=a[6];a[6]=t;
}

这里分析但是讨论是a[7]时候
上述操作应该做循环

for(i=6;i>=0;i--)
{if(a[i+1]<a[i]){t=a[i+1];a[i+1]=a[i];a[i]=t;}elsebreak;
}

这里分析但是讨论是a[8]时候
上述操作应该做循环

for(i=7;i>=0;i--)
{if(a[i+1]<a[i]){t=a[i+1];a[i+1]=a[i];a[i]=t;}elsebreak;
}

前面部分省略，我们整个过程应该是把a[1]到a[8]全部重复上述操作，所以再做循环

for(j=1;j<n;j++)
{for(i=j-1;i>=0;i--){if(a[i+1]>a[i]){t=a[i+1];a[i+1]=a[i];a[i]=t;}elsebreak;}
}

颜老板版本

#include<stdio.h>
double a[1000];void insertsort(int n)
{double t;int i,j;for(j=1;j<n;j++){for(i=j-1;i>=0;i--){if(a[i]>a[i+1]){t=a[i+1];a[i+1]=a[i];a[i]=t;}elsebreak;}}}int main()
{int i,n;printf("输入n的值:");scanf("%d",&n);printf("输入%d个数值\n",n);for(i=0;i<n;i++)scanf("%lf",&a[i]);//调用插入排序insertsort(n);printf("输出排序后的数值【从小到大】\n");for(i=0;i<n;i++)printf("%lf\n",a[i]);return 0;
}

更新版

#include<iostream>using namespace std;const int N=1e5;
int n;
int a[N];void insertSort()
{for(int i=0;i<n-1;i++)for(int j=i+1;j;j--)if(a[j]<a[j-1])swap(a[j],a[j-1]);else break;
}int main()
{cin>>n;for(int i=0;i<n;i++)cin>>a[i];insertSort();for(int i=0;i<n;i++)cout<<a[i];return 0;
}

测试数据

500 218 97 78 13 7 259 14 90 86 460 72 134 458 2 245 490 126 33 355 171 166 433 16 74 436 167 5 296 350 148 146 279 230 467182 31 315 77 151 442 253 224 156 325 379 183 30 47 129 124 441 497 314 193 390 463 80 362 461 280 383 185 415 179 174234 214 1 199 244 249 398 473 136 394 349 369 63 83 356 440 363 219 484 330 425 465 176 125 269 289 312 162 451 480100 342 418 243 177 149 10 422 42 478 338 141 367 346 271 221 283 114 443 216 145 235 220 380 204 147 24 307 285 403175 256 477 305 165 416 420 255 227 211 427 370 223 195 9 69 264 35 17 38 384 56 329 300 246 178 203 39 471 55 46 103 263 455 231 487 445 188 268 482 58 294 257 449 391 500 392 479 261 492 96 267 88 116 494 206 43 262 71 180 120 142 351 29 340 130 310 57 431 226 276 6 437 187 447 270 345 66 374 210 133 348 215 242 419 469 435 37 331 84 59 28 117 430 426 488 222 399 452 448 273 158 150 170 40 110 217 229 232 76 303 382 241 275 108 366 409 499 26 311 302 486 91 347 334 94 358 491 196 107 360 401 292 191 4 297 475 378 298 236 389 22 359 233 163 212 92 53 288 472 476 327 153 278 99 483 115 143 407 205 344 498 316 132 8 190 181 113 160 317 410 48 60 105 127 239 250 400 70 213 377 154 474 319 322 495 44 397 62 313 411 393 164 496 111 51 291 429 172 470 168 54 157 225 208 20 328 417 106 324 135 489 240 326 64 265 404 450 318 98 444 237 308 104 352 155 438 396 152 293 25 371 68 408 432 112 301 73 11 128 354 251 254 87 434 247 34 332 252 192 258 323 412 341 12 385 45 65 228 357 466 281 49 194 284 137 406 372 485 454 123 36 169 209 41 140 353 299 375 402 320 121 459 457 138 75 421 144 274 339 93 207 197 82 61 200 287 364 102 266 50 260 343 373 81 456 198 202 173 388 85 282 23 290 386 333 446 424 189 462 95 468 286 335 361 295 321 368 186 413 10167 131 89 79 439 481 122 118 387 139 27 18 395 52 423 405 381 336 184 414 3 428 119 309 493 453 161 306 15 464 248 109 21 365 376 32 19 272 201 238 159 337 304 277

了解更多

如果你想了解更多的插入排序的逻辑，可以直接参照我写的插入排序，或者在B站查询更多优质UP主的视频，而视频方式的内容或许能让你理解得更快
如果你想了解颜老师要求的六种排序算法，你可以查看我的六种排序
虽然是排序算法，但是此排序算法已经能证明它的思想是 蛮力法。一一比较。
【计划6个排序就只剩下：堆排序】

插入排序的具体写法其实不止一种。
给另外一个思路

所以大家一定要对蛮力法 穷举法 要有一个新的认识。不是一堆for才是蛮力法。

例2 1,2,3,4可以组成那些没有重复的4位数值

分析：当初在大家大一的时候我教过你们的。还记得吗

颜老板版本

方法1：枚举法【蛮力法】

#include<stdio.h>int main()
{//1,2,3,4可以组成那些没有重复的4位数值int a,b,c,d;for(a=1;a<=4;a++)for(b=1;b<=4;b++)for(c=1;c<=4;c++)for(d=1;d<=4;d++){//没有重复，就是指每个位置上的数值不同 if(a!=b && a!=c && a!=d)if(b!=c && b!=d)if(c!=d){printf("%d %d %d %d\n",a,b,c,d);}}return 0;
}

有没有熟悉的味道

但是说一点:

1 书写简单粗暴！

2 如果问题放到1-n的情况，且n自己输入。估计大家都疯了。

注明

没有必要看这个，直接是全排列的概念，nextpermutation即可

方法2：全排列 【今天的重点】

全排列：组合数学中经常用到的，今天介绍程序中的计算序列的全排列的函数
next_permutation(start,end)
和
prev_ permutation(start,end)

start 表示数据的开始位置
end 表示数据的结束位置

以上2个函数作用是一样的
区别在于：
前者是求的是当前排列的下一个排列
后者是求的是当前排列的上一个排列

说明一下 next_permutation和prev_ permutation都隶属于#include
函数原型是：bool next_permutation(iterator start,iterator end)
函数的意义：当 当前序列不存在下一个排列时，则返回false
当 当前序列存在下一个排列时，则返回true

颜老板版本

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>using namespace std;int main()
{int a[4]={1,2,3,4};do{printf("%d %d %d %d\n",a[0],a[1],a[2],a[3]);}while(next_permutation(a,a+4));return 0;
}

由上述代码可以看出
next_permutation(a,a+4)函数，是对数组a中的前4个数组元素进行全排列
且在整个过程中函数改变了数组a中的所有值。

需要给大家最后强调一个知识点：

next_permutation 在使用之前必须对要做排列的数组先按照升序排序。否则只能做出该序列之后的全排列。

（1）全排列的程序都要和数组结合使用

（2）数组中的值必须是升序。

颜老板版本

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>using namespace std;int main()
{int a[4]={4,3,2,1};do{printf("%d %d %d %d\n",a[0],a[1],a[2],a[3]);}while(next_permutation(a,a+4));return 0;
}

上述代码最后只输出了一行数据4 3 2 1 。

---

解决如果是1-n的全排列，且n的值自己输入。

颜老板版本

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>using namespace std;int main()
{int a[10000];int i,n;printf("输入数据的个数:");scanf("%d",&n);//从第0个位置到第n-1个位置依次填入1-n，注意是升序填写 for(i=0;i<n;i++)a[i]=i+1;do{for(i=0;i<n;i++)printf("%d ",a[i]);printf("\n");}while(next_permutation(a,a+n));return 0;
}

提醒：

这里我们使用的数组，数组是有局限性的。
其实这里可以使用指针来写！可以使用malloc实现动态划分存储空间。这个写留给你们自己玩儿。
我上述代码是C++和C的混搭写法！

注明

没有必要看这个，直接是全排列的概念，nextpermutation即可

下课内容

例3 0/1背包问题

【算法中非常经典的一个例子。】
【回朔法，动态规划等】

有n个重量分别是w1,w2…,wn的物品（物品编号为1-n）
它们的价值分别为v1,v2,…,vn
给定一个容量为W的背包。
设计从这些物品中选取一部分放入该背包的方案。
每个物品要么选中要么不选中，【意味着：说明每个物品只有1样】
要求选中的物品不仅能够放在背包中，而且具有最大的价值。
并对如下所展示的5个物品求出W不超过10时的最佳解。
物品编号 重量 价值
1 2 6
2 2 3
3 6 5
4 5 4
5 4 6

方法1：枚举法【蛮力法】 作为作业

方法2：全排列
//先详细讨论11111组合的全排列。
//注意，整个过程物品1到5的选中状态是由s决定的。
//选中 ‘1’ 注意是字符型
//没有选中 ‘0’ 注意是字符型

if(s[0]=='1')ww=ww+w[0];
elseww=ww;if(s[0]=='1')vv=vv+v[0];
elsevv=vv;

上述写法很low，一看都是初级程序员写的。
所以改进上述写法

---

if(s[0]=='1')ww=ww+1*w[0];
elseww=ww+0*w[0];if(s[0]=='1')vv=vv+1*v[0];
elsevv=vv+0*v[0];

---

这里的1*和0*是由s[0]的值决定，
如果s[0]的值是'1' 则1*
如果s[0]的值是'0' 则0*

---

所以做'1'变1 '0'变0
'1'-48=1
'0'-48=0
所以去掉if和else

---

ww=ww+(s[0]-48)*w[0];ww=ww+(s[0]-48)*w[0];vv=vv+(s[0]-48)*v[0];vv=vv+(s[0]-48)*v[0];

既然一样，就留一个就好了嘛

---

ww=ww+(s[0]-48)*w[0];
vv=vv+(s[0]-48)*v[0];

---

对比起来很明显下面的写法高大上。

ww+=(s[0]-48)*w[0];
vv+=(s[0]-48)*v[0];

---

最后上述操作做循环

do
{for(i=0;i<n;i++){ww+=(s[i]-48)*w[i];vv+=(s[i]-48)*v[i];}if(ww<=W && vv>maxv)//ww当前背包重量不能超过背包容量，且vv当前背包物品价值大于之前的最大价价值 {maxv=vv;str=s;//这时的s的组合我要记录下来 }//一种排列组合计算结束后 vv和ww要清零ww=0;vv=0;	 
}while(next_permutation(s.begin(),s.end()));

//意味着组合为11111的全部选中处理结束，接下来我们处理的是01111组合,必须要保证组合的起始排列是升序的 
s[0]='0';

提醒上述代码只是处理11111
我们还要接着处理01111，00111,00011,00001,00000【必须保证其他组合的初始状态是升序】

所以上述代码 再做循环！五次

代码如下

颜老板版本

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>using namespace std;int main()
{int W=10,n=5;//W表示背包可以承载的最大重量，n表示一共有5个物品int w[5]={2,2,6,5,4};//用数组w依次存储物品1-5的重量int v[5]={6,3,5,4,6};//用数组v依次存储物品1-5的价值//在整个问题中，最大的一个在意点是：每个物品选中还是没有选中string s="11111"; // 一开始假设5个物品都被选中//一共存在着五个选中，4个选中，3个选中，2个选中，1个选中，0个选中int i,j;int ww=0;//ww计算当前背包中已有物品的重量 int vv=0;//vv计算当前背包中已有物品的价值int maxv=0;//当前最大价值的总数string str;//存放最后的最大价值的选中情况for(j=0;j<n;j++)//因为s中有5个位置要给0 { do{for(i=0;i<n;i++){ww+=(s[i]-48)*w[i];vv+=(s[i]-48)*v[i];}if(ww<=W && vv>maxv)//ww当前背包重量不能超过背包容量，且vv当前背包物品价值大于之前的最大价价值 {maxv=vv;str=s;//这时的s的组合我要记录下来 }//一种排列组合计算结束后 vv和ww要清零ww=0;vv=0;	 }while(next_permutation(s.begin(),s.end()));//意味着组合为11111的全部选中处理结束，接下来我们处理的是01111组合,必须要保证组合的起始排列是升序的 s[j]='0'; }cout<<str<<endl;cout<<maxv<<endl;return 0;
}

更新版

方法一：字符串蛮力

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;int main()
{int W = 10, n = 5;int w[5] = { 2,2,6,5,4 }, v[5] = { 6,3,5,4,6 };string pres = "00000";int ww = 0, vv = 0, maxv = 0;string str;char s[1000];for (int j = 0; j < 5; j++)for (int a = 0; a < 5; a++)for (int b = 0; b < 5; b++)for (int c = 0; c < 5; c++)for (int d = 0; d < 5; d++)for (int e = 0; e < 5; e++){if (a != b && a != c && a != d && a != e);if (b != c && b != d && b != e);if (c != d && c != e);if (d != e);pres[j]='1';s[0] = pres[a]; s[1] = pres[b]; s[2] = pres[c]; s[3] = pres[d]; s[4] = pres[e];//cout << s[0] << " " << s[1] << " " << s[2] << " " << s[3] << " " << s[4] << " " << endl;for (int i = 0; i < 5; i++)ww += (s[i] - '0')*w[i], vv += (s[i] - '0')*v[i];//当前背包重量不超过容量，且vv当前背包价值大于最大价值if (ww <= W && vv > maxv)maxv = vv, str = s;//记录此时的s的组合vv = 0, ww = 0;}for (int i = 0; i < 5; i++)cout << str[i];cout << endl;cout << maxv << endl;return 0;
}

方法二：二进制枚举

#include<iostream>using namespace std;int ww,vv,maxv,strres;int main()
{int W = 10;int w[5] = { 2,2,6,5,4 }, v[5] = { 6,3,5,4,6 };for(int i=0;i<1<<5;i++)//二进制最大可能选择数{for(int j=0;j<5;j++)ww += (i>>j&1)*w[j], vv += (i>>j&1)*v[j];/判断当前位子是否被选择,更新0或1倍目标值的数值if (ww <= W && vv > maxv)maxv = vv,strres=i;//更新vv = 0, ww = 0;}for(int i=0;i<5;i++)cout<<(strres>>i&1);//因为是选择情况，所以直接输出cout<<endl;cout << maxv;return 0;
}

方法三：DFS

无法保存最大路径

#include<iostream>using namespace std;int ww,vv,maxv,strres;
int W = 10;
int w[5] = { 2,2,6,5,4 }, v[5] = { 6,3,5,4,6 };int str[5];
int ans[5];void dfs(int tw,int ans)
{if(tw<=W&&ans > maxv){maxv = ans;return ;}for(int i=0;i<5;i++)if(!str[i]&&tw>=w[i]){str[i]=1;dfs(tw-w[i],ans+v[i]);str[i]=0;}}
int main()
{dfs(W,0);cout << maxv;return 0;
}

三.２闫老板思考角度

#include<iostream>using namespace std;int w[5] = { 2,2,6,5,4 }, v[5] = { 6,3,5,4,6 };int x[5];
int maxv = 0;
int ans[5];void dfs(int i, int ww, int vv)
{if (i == 5)if (ww <= 10 && vv > maxv) { maxv = vv; for(int i=0;i<5;i++)ans[i]=x[i];return; }//记录最优状态else return;//这里给他加了个退出x[i] = 1;dfs(i + 1, ww + w[i], vv + v[i]);x[i]=0;dfs(i + 1, ww, vv);
}int main()
{dfs(0, 0, 0);for(auto x:ans)cout<<x;cout<<endl;cout << maxv;return 0;
}

方法四：全排列

利用next_permuatation的特性，全排列，而我们只需要截取前面五位的状态即可

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int main()
{int W = 10, n = 5;int w[5] = {2, 2, 6, 5, 4}, v[5] = {6, 3, 5, 4, 6};string s = "0000011111";int ww = 0, vv = 0, maxv = 0;string str;for (int j = 0; j < n; j++){do{for (int i = 0; i < n; i++)ww += (s[i] - '0') * w[i], vv += (s[i] - '0') * v[i];//当前背包重量不超过容量，且vv当前背包价值大于最大价值if (ww <= W && vv > maxv)maxv = vv, str = s; //记录此时的s的组合vv = 0, ww = 0;} while (next_permutation(s.begin(),s.end()));}for(int i=0;i<5;i++)cout << str[i];cout<<endl;cout << maxv;return 0;
}

方法五：数组蛮力

利用数组表示01

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;
int s[5];int main()
{int W = 10, n = 5;int w[5] = { 2,2,6,5,4 }, v[5] = { 6,3,5,4,6 };int ww = 0, vv = 0, maxv = 0;string str;for (s[0]=0; s[0] < 2; s[0]++)for (s[1]=0; s[1] < 2; s[1]++)for (s[2]=0; s[2] < 2; s[2]++)for (s[3]=0; s[3] < 2; s[3]++)for (s[4]=0; s[4] < 2; s[4]++){for (int i = 0; i < 5; i++)ww += (s[i])*w[i], vv += (s[i])*v[i];if (ww <= W && vv > maxv)maxv = vv;vv = 0, ww = 0;}cout << maxv << endl;getchar(); getchar();return 0;
}

答案

11001
15

了解更多

如果你对下课部分的内容有更多的疑惑，或者说不大看的明白我的写法，请看五种蛮力法解决01背包问题