0

一.动态规划求解0-1背包问题 /************************************************************************/ /* 0-1背包问题： /* 给定n种物品和一个背包 /* 物品i的重量为wi，其价值为vi /* 背包的容量为c /* 应如何选择装入背包的物品，使得装入背包中的物品 /* 的总价值最大？ /* 注：在选择装入背包的物品时，对物品i只有两种选择， /* 即装入或不装入背包。

不能将物品i装入多次，也 /* 不能只装入部分的物品i。

/* /* 1. 0-1背包问题的形式化描述： /* 给定c>0, wi>0, vi>0, 0 sum_{i=2 to n} (vi*yi) /* 且，w1*y1 + sum_{i=2 to n} (wi*zi) sum_{i=1 to n} (vi*yi) /* w1*y1 + sum_{i=2 to n} (wi*zi) =wn /* m(n,j) = 0, 0=wi，则在不装物品i和装入物品i之间做出选择 /* 不装物品i的最优值：m(i+1,j) /* 装入物品i的最优值：m(i+1, j-wi) + vi /* 所以： /* m(i,j) = max {m(i+1,j), m(i+1, j-wi) + vi}, j>=wi /* /************************************************************************/ #define max(a,b) (((a) > (b)) ? (a) : (b)) #define min(a,b) (((a) void Knapsack(Type* v, int *w, int c, int n, Type **m) { //递归初始条件 int jMax = min(w[n] - 1, c); for (int j=0; j=wi和01; i--) { jMax = min(w[i] - 1, c); for (int j=0; j= w[1]) { m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]); } } template void TraceBack(Type **m, int *w, int c, int n, int* x) { for (int i=1; i(v, w, c, n, ppm); TraceBack(ppm, w, c, n, x); return 0； } 二.贪心算法求解0-1背包问题 1.贪心法的基本思路： ——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。

当达到某算法中的某一步不能再继续前进时，算法停止。

该算法存在问题： 1）.不能保证求得的最后解是最佳的； 2）.不能用来求最大或最小解问题； 3）.只能求满足某些约束条件的可行解的范围。

实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解； 2.例题分析 1）.[背包问题]有一个背包，背包容量是M=150。

有7个物品，物品可以分割成任意大小。

要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 分析： 目标函数： ∑pi最大 约束条件是装入的物品总重量不超过背包容量：∑wi（环境：c++） #include...

lingo旅行售货员问题最后回到终点

MODEL:SETS:city/A1..A8/:U;links(city,city):distance,X;ENDSETSDATA: distance=0 300 360 210 590 475 500 690300 0 380 270 230 285 200 390 360 380 0 510 230 765 580 770210 270 510 0 470 265 450 640590 230 230 370 0 515 260 450475 285 765 265 515 0 460 650500 200 580 450 260 460 0 190690 390 760 640 450 650 190 0;ENDDATAn=@SIZE(city);MIN=@SUM(links:distance*X);@FOR(city(k):@SUM(city(i)|i#ne#k:x(i,k))=1;@SUM(city(j)|j#ne#k:x(k,j))=1;@FOR(city(j)|j#gt#1 #and# j#ne#k:U(j)>=U(k)+X(k,j)-(N-2)*(1-X(k,j))+(N-3)*X(j,k)););@FOR(links:@BIN(x));@FOR(city(k)|k#gt#1:U(k)<=N-1-(N-2)*X(1,k);U(k)>=1+(N-2)*X(k,1));END

用回溯法和分支限界法求对称的旅行商问题

MODEL:SETS:city/A1..A8/:U;links(city,city):distance,X;ENDSETSDATA: distance=0 300 360 210 590 475 500 690300 0 380 270 230 285 200 390 360 380 0 510 230 765 580 770210 270 510 0 470 265 450 640590 230 230 370 0 515 260 450475 285 765 265 515 0 460 650500 200 580 450 260 460 0 190690 390 760 640 450 650 190 0;ENDDATAn=@SIZE(city);MIN=@SUM(links:distance*X);@FOR(city(k):@SUM(city(i)|i#ne#k:x(i,k))=1;@SUM(city(j)|j#ne#k:x(k,j))=1;@FOR(city(j)|j#gt#1 #and# j#ne#k:U(j)>=U(k)+X(k,j)-(N-2)*(1-X(k,j))+(N-3)*X(j,k)););@FOR(links:@BIN(x));@FOR(city(k)|k#gt#1:U(k)<=N-1-(N-2)*X(1,k);U(k)>=1+(N-2)*X(k,1));END

求教C语言回溯法写出八皇后问题的92种解

(1)全排列 将自然数1~n进行排列，共形成n！中排列方式，叫做全排列。

例如3的全排列是：1/2/3、1/3/2、2/1/3、2/3/1、3/1/2、3/2/1，共3!=6种。

（2）8皇后（或者n皇后） 保证8个皇后不能互相攻击，即保证每一横行、每一竖行、每一斜行最多一个皇后。

我们撇开第三个条件，如果每一横行、每一竖行都只有一个皇后。

将8*8棋盘标上坐标。

我们讨论其中的一种解法： - - - - - - - Q - - - Q - - - - Q - - - - - - - - - Q - - - - - - - - - - Q - - - Q - - - - - - - - - - - - Q - - - - - Q - - - 如果用坐标表示就是：（1,8） (2,4) (3,1) (4,3) (5,6) (6,2) (7,7) (8,5) 将横坐标按次序排列，纵坐标就是8/4/1/3/6/2/7/5。

这就是1~8的一个全排列。

我们将1~8的全排列存入输入a[]中（a[0]~a[7]），然后8个皇后的坐标就是（i+1,a[i]），其中i为0~7。

这样就能保证任意两个不会同一行、同一列了。

置于斜行，你知道的，两个点之间连线的斜率绝对值为1或者-1即为同一斜行，充要条件是|x1-x2|=|y1-y2|（两个点的坐标为（x1,y1）(x2,y2)）。

我们在输出的时候进行判断，任意两个点如果满足上述等式，则判为失败，不输出。

下面附上代码：添加必要的注释，其中全排列的实现看看注释应该可以看懂： #include#include#include#includeint printed；//该函数用于画图，这里为了节约空间则略去//读者只需要将draw(a,k)；去掉注释即可画图void draw(int* a,int k){ int i,j; for(i=0;i<k;i++) { printf(＂\t＂); for(j=0;j<k;j++) //有皇后输出Q，否则输出- if(a[i]-1==j) printf(＂Q ＂); else printf(＂- ＂); printf(＂\n＂); } printf(＂\n＂)；}//递归实现全排列，a是数组，iStep是位置的测试点，k是皇后的个数，一般等于8void Settle(int *a,int iStep,int k){ int i,j,l,flag=1； //如果iStep的数字等于a之前的数字，则存在重复，返回 for(i=0;i<iStep-1;i++) if(a[iStep-1]==a[i]) return； //如果iStep==k，即递归结束到最后一位，可以验证是否斜行满足 if(iStep==k) { //双重循环判断是否斜行满足 for(j=0;j<k;j++) for(l=0;l<k&&l!=j;l++) //如果不满足，则flag=0 if(fabs(j-l)==fabs(a[j]-a[l])) flag=0； //如果flag==1，则通过了斜行的所有测试，输出。

if(flag) { for(i=0;i<k;i++) printf(＂(%d,%d) ＂,i+1,a[i]); printf(＂\n＂)； //如果去掉这里的注释可以获得画图，由于空间不够，这里略去 // draw(a,k); //printed变量计算有多少满足题意的结果，是全局变量 printed++; } flag=1； } //如果未测试至最后末尾，则测试下一位（递归） for(i=1;i<=k;i++) { a[iStep]=i; Settle(a,iStep+1,k); }}void main(){ int* a; int k； //输入维数，建立数组 printf(＂Enter the size of the square:＂); scanf(＂%d＂,&k); a=(int*)calloc(k,sizeof(int)）； //清屏，从iStep=0处进入递归 system(＂cls＂); Settle(a,0,k)； //判断最后是否有结果 if(! printed) printf(＂No answers accepted!\n＂); else printf(＂%d states available!\n＂,printed)；}附输出结果（输入k=8）:(1,1) (2,5) (3,8) (4,6) (5,3) (6,7) (7,2) (8,4)(1,1) (2,6) (3,8) (4,3) (5,7) (6,4) (7,2) (8,5)(1,1) (2,7) (3,4) (4,6) (5,8) (6,2) (7,5) (8,3)(1,1) (2,7) (3,5) (4,8) (5,2) (6,4) (7,6) (8,3)(1,2) (2,4) (3,6) (4,8) (5,3) (6,1) (7,7) (8,5)(1,2) (2,5) (3,7) (4,1) (5,3) (6,8) (7,6) (8,4)(1,2) (2,5) (3,7) (4,4) (5,1) (6,8) (7,6) (8,3)(1,2) (2,6) (3,1) (4,7) (5,4) (6,8) (7,3) (8,5)(1,2) (2,6) (3,8) (4,3) (5,1) (6,4) (7,7) (8,5)(1,2) (2,7) (3,3) (4,6) (5,8) (6,5) (7,1) (8,4)(1,2) (2,7) (3,5) (4,8) (5,1) (6,4) (7,6) (8,3)(1,2) (2,8) (3,6) (4,1) (5,3) (6,5) (7,7) (8,4)(1,3) (2,1) (3,7) (4,5) (5,8) (6,2) (7,4) (8,6)(1,3) (2,5) (3,2) (4,8) (5,1) (6,7) (7,4) (8,6)(1,3) (2,5) (3,2) (4,8) (5,6) (6,4) (7,7) (8,1)(1,3) (2,5) (3,7) (4,1) (5,4) (6,2) (7,8) (8,6)(1,3) (2,5) (3,8) (4,4) (5,1) (6,7) (7,2) (8,6)(1,3) (2,6) (3,2) (4,5) (5,8) (6,1) (7,7) (8,4)(1,3) (2,6) (3,2) (4,7) (5,1) (6,4) (7,8) (8,5)(1,3) (2,6) (3,2) (4,7) (5,5) (6,1) (7,8) (8,4)(1,3) (2,6) (3,4) (4,1) (5,8) (6,5) (7,7) (8,2)(1,3) (2,6) (3,4) (4,2) (5,8) (6,5) (7,7) (8,1)(1,3) (2,6) (3,8) (4,1) (5,4) (6,7) (7,5) (8,2)(1,3) (2,6) (3,8) (4,1) (5,5) (6,7) (7,2) (8,4)(1,3) (2,6) (3,8) (4,2) (5,4) (6,1) (7,7) (8,5)(1,3) (2,7) (3,2) (4,8) (5,5) (6,1) (7,4) (8,6)(1,3) (2,7) (3,2) (4,8) (5,6) (6,4) (7,1) (8,5)(1,3) (2,8) (3,4) (4,7) (5,1) (6,6) (7,2) (8,5)(1,4) (2,1) (3,5) (4,8) (5,2) (6,7) (7,3) (8,6)(1,4) (2,1) (3,5) (4,8) (5,6) (6,3) (7,7) (8,2)(1,4) (2,2) (3,5) (4,8) (5,6) (6,1) (7,3) (8,7)(1,4) (2,2) (3,7) (4,3) (5,6) (6,8) (7,1) (8,5)(1,4) (2,2) (3,7) (4,3) (5,6) (6,8) (7,5) (8,1)(1,4) (2,2) (3,7) (4,5) (5,1) (6,8) (7,6) (8,3)(1,4) (2,2) (3,8) (4,5) (5,7) (6,1) (7,3) (8,6)(1,4) (2,2) (3,8) (4,6) (5,1) (6,3) (7,5) (8,7)(1,4) (2,6) (3,1) (4,5) (5,2) (6,8) (7,3) (8,7)(1,4) (2,6) (3,8) (4,2) (5,7) (6,1) (7,3) (8,5)(1,4) (2,6) (3,8) (4,3) (5,1) (6,7) (7,5) (8,2)(1,4) (2,7) (3,1) (4,8) (5,5) (6,2) (7,6) (8,3)(1,4) (2,7) (3,3) (4,8) (5,2) (6,5) (7,1) (8,6)(1,4) (2,7) (3,5) (4,2) (5,6) (6,1) (7,3) (8,8)(1,4) (2,7) (3,5) (4,3) (5,1) (6,6) (7,8) (8,2)(1,4) (2,8) (3,1) (4,3) (5,6) (6,2) (7,7) (8,5)(1,4) (2,8) (3,1) (4,5) (5,7) (6,2) (7,6) (8,3)(1,4) (2,8) (3,5) (4,3) (5,1) (6,7) (7,2) (8,6)(1,5) (2,1) (3,4) (4,6) (5,8) (6,2) (7,7) (8,3)(1,5) (2,1) (3,8) (4,4) (5,2) (6,7) (7,3) (8,6)(1,5) (2,1) (3,8) (4,6) (5,3) (6,7) (7,2) (8,4)(1,5) (2,2) (3,4) (4,6) (5,8) (6,3) (7,1) (8,7)(1,5) (...

谁能用比较通俗的语言讲解一下回溯法？

TSP问题（旅行商问题）是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短.假设现在有四个城市，0,1,2,3，他们之间的代价如图一，可以存成二维表的形式：现在要从城市0出发，最后又回到0，期间1,2,3都必须并且只能经过一次，使代价最小.这就是旅行者问题.可以利用回溯法，分值界限等方法解决！

在时间复杂度上比较分支限界法和回溯法？

楼上的不要瞎说，分支界限和回溯都是两种不同的搜索方法，属于并列的，不是谁包含谁，1）回溯法一般是采用深度优先搜索解空间，采用限界函数进行剪枝2）分支界限一般是采用广度优先搜索解空间，采用优先队列进行剪枝回溯法中解空间中节点可以多次出现，而分支界限只会出现一次，不会发生回溯，你怎么说分支界限就是回溯呢...