回溯算法代码
A. 分别用回溯法和动态规划求0/1背包问题（c语言代码）
#include <stdio.h>
#include <malloc.h>
#include <windows.h>typedef struct goods
{
double *value; //价值
double *weight; //重量
char *select; //是否选中到方案
int num;//物品数量
double limitw; //限制重量
}GOODS;
double maxvalue,totalvalue;//方案最大价值,物品总价值
char *select1; //临时数组
void backpack(GOODS *g, int i, double tw, double tv)//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值
{
int k;
if (tw + g->weight[i] <= g->limitw)//将物品i包含在当前方案,且重量小于等于限制重量
{
select1[i] = 1; //选中第i个物品
if (i < g->num - 1) //若物品i不是最后一个物品
backpack(g, i + 1, tw + g->weight[i], tv); //递归调用,继续添加下一物品
else //若已到最后一个物品
{
for (k = 0; k < g->num; ++k) //将状态标志复制到option数组中
g->select[k] = select1[k];
maxvalue = tv; //保存当前方案的最大价值
}
}
select1[i] = 0; //取消物品i的选择状态
if (tv - g->value[i] > maxvalue)//若物品总价值减去物品i的价值还大于maxv方案中已有的价值,说明还可以继续向方案中添加物品
{
if (i < g->num - 1) //若物品i不是最后一个物品
backpack(g, i + 1, tw, tv - g->value[i]); //递归调用,继续加入下一物品
else //若已到最后一个物品
{
for (k = 0; k < g->num; ++k) //将状态标志复制到option数组中
g->select[k] = select1[k];
maxvalue = tv - g->value[i]; //保存当前方案的最大价值(从物品总价值中减去物品i的价值)
}
}
}
int main()
{
double sumweight;
GOODS g;
int i;
printf("背包最大重量:");
scanf("%lf",&g.limitw);
printf("可选物品数量:");
scanf("%d",&g.num);
if(!(g.value = (double *)malloc(sizeof(double)*g.num)))//分配内存保存物品价值
{
printf("内存分配失败\n");
exit(0);
}
if(!(g.weight = (double *)malloc(sizeof(double)*g.num)))//分配内存保存物品的重量
{
printf("内存分配失败\n");
exit(0);
}
if(!(g.select = (char *)malloc(sizeof(char)*g.num)))//分配内存保存物品的重量
{
printf("内存分配失败\n");
exit(0);
}
if(!(select1 = (char *)malloc(sizeof(char)*g.num)))//分配内存保存物品的重量
{
printf("内存分配失败\n");
exit(0);
}
totalvalue=0;
for (i = 0; i < g.num; i++)
{
printf("输入第%d号物品的重量和价值:",i + 1);
scanf("%lf%lf",&g.weight[i],&g.value[i]);
totalvalue+=g.value[i];//统计所有物品的价值总和
}
printf("\n背包最大能装的重量为:%.2f\n\n",g.limitw);
for (i = 0; i < g.num; i++)
printf("第%d号物品重:%.2f,价值:%.2f\n", i + 1, g.weight[i], g.value[i]);
for (i = 0; i < g.num; i++)//初始设各物品都没加入选择集
select1[i]=0;
maxvalue=0;//加入方案物品的总价值
backpack(&g,0,0.0,totalvalue); //第0号物品加入方案,总重量为0,所有物品价值为totalvalue
sumweight=0;
printf("\n可将以下物品装入背包,使背包装的物品价值最大:\n");
for (i = 0; i < g.num; ++i)
if (g.select[i])
{
printf("第%d号物品,重量:%.2f,价值:%.2f\n", i + 1, g.weight[i], g.value[i]);
sumweight+=g.weight[i];
}
printf("\n总重量为: %.2f,总价值为:%.2f\n", sumweight, maxvalue );
// getch();
return 0;
}
B. 求教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<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
intprinted;
//该函数用于画图，这里为了节约空间则略去
//读者只需要将draw(a,k);去掉注释即可画图
voiddraw(int*a,intk)
{
inti,j;
for(i=0;i<k;i++)
{
printf(" ");
for(j=0;j<k;j++)
//有皇后输出Q，否则输出-
if(a[i]-1==j)printf("Q");elseprintf("-");
printf(" ");
}
printf(" ");
}
//递归实现全排列,a是数组，iStep是位置的测试点，k是皇后的个数，一般等于8
voidSettle(int*a,intiStep,intk)
{
inti,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(" ");
//如果去掉这里的注释可以获得画图，由于空间不够，这里略去
// draw(a,k);
//printed变量计算有多少满足题意的结果，是全局变量
printed++;
}
flag=1;
}
//如果未测试至最后末尾，则测试下一位（递归）
for(i=1;i<=k;i++)
{
a[iStep]=i;
Settle(a,iStep+1,k);
}
}
voidmain()
{
int*a;
intk;
//输入维数，建立数组
printf("Enterthesizeofthesquare:");
scanf("%d",&k);
a=(int*)calloc(k,sizeof(int));
//清屏，从iStep=0处进入递归
system("cls");
Settle(a,0,k);
//判断最后是否有结果
if(!printed)printf("Noanswersaccepted! ");
elseprintf("%dstatesavailable! ",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)(2,2)(3,4)(4,7)(5,3)(6,8)(7,6)(8,1)
(1,5)(2,2)(3,6)(4,1)(5,7)(6,4)(7,8)(8,3)
(1,5)(2,2)(3,8)(4,1)(5,4)(6,7)(7,3)(8,6)
(1,5)(2,3)(3,1)(4,6)(5,8)(6,2)(7,4)(8,7)
(1,5)(2,3)(3,1)(4,7)(5,2)(6,8)(7,6)(8,4)
(1,5)(2,3)(3,8)(4,4)(5,7)(6,1)(7,6)(8,2)
(1,5)(2,7)(3,1)(4,3)(5,8)(6,6)(7,4)(8,2)
(1,5)(2,7)(3,1)(4,4)(5,2)(6,8)(7,6)(8,3)
(1,5)(2,7)(3,2)(4,4)(5,8)(6,1)(7,3)(8,6)
(1,5)(2,7)(3,2)(4,6)(5,3)(6,1)(7,4)(8,8)
(1,5)(2,7)(3,2)(4,6)(5,3)(6,1)(7,8)(8,4)
(1,5)(2,7)(3,4)(4,1)(5,3)(6,8)(7,6)(8,2)
(1,5)(2,8)(3,4)(4,1)(5,3)(6,6)(7,2)(8,7)
(1,5)(2,8)(3,4)(4,1)(5,7)(6,2)(7,6)(8,3)
(1,6)(2,1)(3,5)(4,2)(5,8)(6,3)(7,7)(8,4)
(1,6)(2,2)(3,7)(4,1)(5,3)(6,5)(7,8)(8,4)
(1,6)(2,2)(3,7)(4,1)(5,4)(6,8)(7,5)(8,3)
(1,6)(2,3)(3,1)(4,7)(5,5)(6,8)(7,2)(8,4)
(1,6)(2,3)(3,1)(4,8)(5,4)(6,2)(7,7)(8,5)
(1,6)(2,3)(3,1)(4,8)(5,5)(6,2)(7,4)(8,7)
(1,6)(2,3)(3,5)(4,7)(5,1)(6,4)(7,2)(8,8)
(1,6)(2,3)(3,5)(4,8)(5,1)(6,4)(7,2)(8,7)
(1,6)(2,3)(3,7)(4,2)(5,4)(6,8)(7,1)(8,5)
(1,6)(2,3)(3,7)(4,2)(5,8)(6,5)(7,1)(8,4)
(1,6)(2,3)(3,7)(4,4)(5,1)(6,8)(7,2)(8,5)
(1,6)(2,4)(3,1)(4,5)(5,8)(6,2)(7,7)(8,3)
(1,6)(2,4)(3,2)(4,8)(5,5)(6,7)(7,1)(8,3)
(1,6)(2,4)(3,7)(4,1)(5,3)(6,5)(7,2)(8,8)
(1,6)(2,4)(3,7)(4,1)(5,8)(6,2)(7,5)(8,3)
(1,6)(2,8)(3,2)(4,4)(5,1)(6,7)(7,5)(8,3)
(1,7)(2,1)(3,3)(4,8)(5,6)(6,4)(7,2)(8,5)
(1,7)(2,2)(3,4)(4,1)(5,8)(6,5)(7,3)(8,6)
(1,7)(2,2)(3,6)(4,3)(5,1)(6,4)(7,8)(8,5)
(1,7)(2,3)(3,1)(4,6)(5,8)(6,5)(7,2)(8,4)
(1,7)(2,3)(3,8)(4,2)(5,5)(6,1)(7,6)(8,4)
(1,7)(2,4)(3,2)(4,5)(5,8)(6,1)(7,3)(8,6)
(1,7)(2,4)(3,2)(4,8)(5,6)(6,1)(7,3)(8,5)
(1,7)(2,5)(3,3)(4,1)(5,6)(6,8)(7,2)(8,4)
(1,8)(2,2)(3,4)(4,1)(5,7)(6,5)(7,3)(8,6)
(1,8)(2,2)(3,5)(4,3)(5,1)(6,7)(7,4)(8,6)
(1,8)(2,3)(3,1)(4,6)(5,2)(6,5)(7,7)(8,4)
(1,8)(2,4)(3,1)(4,3)(5,6)(6,2)(7,7)(8,5)
92statesavailable!
C. c语言回溯算法
if(n==7||a[n+1][i]!=1&&a[n+1][i+1]!=1&&a[n+1][i-1]!=1)
这行的代码是判断是否可以放皇后的句子。如果可以就将所在位置置 1 。后面也就是这样做判断的。这个程序应当有问题，其中try应当是C语言中一个关键字啊，不可以这么用。
就我的看法：八皇后的问题应当用递归加回溯会都到更好的代码，我写过，不过也快忘了。
D. java或者C/C++怎么用回溯法解决最小长度电路板排列问题
以java为例，希望能够帮到你。
电路板排列问题
问题描述
将n块电路板以最佳排列方式插入带有n个插槽的机箱中。n块电路板的不同排列方式对应于不同的电路板插入方案。设B={1, 2, …, n}是n块电路板的集合，L={N1, N2, …, Nm}是连接这n块电路板中若干电路板的m个连接块。Ni是B的一个子集，且Ni中的电路板用同一条导线连接在一起。设x表示n块电路板的一个排列，即在机箱的第i个插槽中插入的电路板编号是x[i]。x所确定的电路板排列Density (x)密度定义为跨越相邻电路板插槽的最大连线数。
例：如图，设n=8, m=5，给定n块电路板及其m个连接块：B={1, 2, 3, 4, 5, 6, 7, 8}，N1={4, 5, 6}，N2={2, 3}，N3={1, 3}，N4={3, 6}，N5={7, 8};其中两个可能的排列如图所示，则该电路板排列的密度分别是2，3。
E. 急需C++代码！作业分配（回溯法）
回溯搜索的非递归思路及实例源码，这是一个通用框架！
http://hi..com/gropefor/blog/item/5d2636542b36e6ccb745ae34.html
F. 硬币兑换问题回溯法伪代码
A数组用来存放硬币,数值1代表正面，0代表反面；
static int s;s是存放每列状态的数初始为0代表一列都没翻，第几位为1就代表第几列被翻转
int turncoin(A,S,N，n) //A(N*9数组） ，N是行数 n代表当次翻哪一列 初次调用n=0，代表第一列
{ int i=1;//因为每列只有两种状态，所以每列只翻一次
static int max=0;//用来存放翻转后正面朝上的最大硬币数；
static int S;//大S用来存储当前硬币堆的翻转状态
do {turncoin(A,S,N，n+1);if （n==8）{ int tem=sum //sum为遍历A数组,所有元素之和（即为当前正面朝上的硬币数)
if（sum>max）{S=s; //把当前翻转状态存储到S,S内总是存储着拥有正面朝上硬币数量最高的一种翻转状态；}}}while(i--&&transform(N，n));
//transform()函数翻转第N列的硬币 并且对s的第n位置一 成功返回ture 并且对是 实现就是for(i=0；
i
拓展资料：
一、题目描述：
一个翻硬币的游戏，有N(N <=10000）行硬币，每行有九个硬币，排成一个N*9的方阵，有的硬币正面朝上，有的反面朝上。我们每次可把一整行或者一整列的所有硬币翻过来，请问怎么翻，使得正面朝上的硬币尽量多（翻硬币无次数限制）。
二、思路分析：
枚举2^9种列的翻法。
遍历N行，如果某行正面朝上的少，翻之；如果正面朝上的多，不翻
记下使得正面最多的方法即可
耗时O(2^9 * N)
这个得到的是最优解.用位运算效率还是很高的.
对每一列,都用一个9位的数表示,一共有N个
然后便利所有的9位状态,(000000000)-(111111111) (二进制)
对于每个状态,都与这N个数异或,每次异或后累加所有的1的值假设为k,如果k小于5则k=9-k.
对N个数累加所有的k,得到最终累加和.
求出所有状态下累加和最大的,就是正面朝上的硬币尽量多的个数.
翻面的方法横列分别是最优解的8位状态和与之对应的每个数异或后累加和k是否小于5.
G. 回溯算法 求1-20这2个数摆成环，要求相邻的两个数的和是素数。我的代码如下：没有语法错误，但是死循环
intsearch(int)、intprint()、intmain()这三个函数名前都有返回值类型符，但函数体内却都没有返回语句。你也写复杂了，下面的代码就可以了：
#include"stdio.h"
intprime(intn){
inti;
if(n>2&&!(n&1)||n<2)
return0;
for(i=3;i*i<=n;i+=2)
if(!(n%i))
return0;
return1;
}
intmain(void){
inti,j;
for(i=1;i<20;i++)
if(prime(j=(i<<1)+1))
printf("%2d+%2d=%2d ",i,i+1,j);
return0;
}
H. 0-1背包问题的多种解法代码（动态规划、贪心法、回溯法、分支限界法）
一.动态规划求解0-1背包问题
/************************************************************************/
/* 0-1背包问题：
/* 给定n种物品和一个背包
/* 物品i的重量为wi，其价值为vi
/* 背包的容量为c
/* 应如何选择装入背包的物品，使得装入背包中的物品
/* 的总价值最大？
/* 注：在选择装入背包的物品时，对物品i只有两种选择，
/* 即装入或不装入背包。不能将物品i装入多次，也
/* 不能只装入部分的物品i。
/*
/* 1. 0-1背包问题的形式化描述：
/* 给定c>0, wi>0, vi>0, 0<=i<=n，要求找到一个n元的
/* 0-1向量(x1, x2, ..., xn), 使得：
/* max sum_{i=1 to n} (vi*xi),且满足如下约束：
/* (1) sum_{i=1 to n} (wi*xi) <= c
/* (2) xi∈{0, 1}, 1<=i<=n
/*
/* 2. 0-1背包问题的求解
/* 0-1背包问题具有最优子结构性质和子问题重叠性质，适于
/* 采用动态规划方法求解
/*
/* 2.1 最优子结构性质
/* 设(y1,y2,...,yn)是给定0-1背包问题的一个最优解，则必有
/* 结论，(y2,y3,...,yn)是如下子问题的一个最优解：
/* max sum_{i=2 to n} (vi*xi)
/* (1) sum_{i=2 to n} (wi*xi) <= c - w1*y1
/* (2) xi∈{0, 1}, 2<=i<=n
/* 因为如若不然，则该子问题存在一个最优解(z2,z3,...,zn)，
/* 而(y2,y3,...,yn)不是其最优解。那么有：
/* sum_{i=2 to n} (vi*zi) > sum_{i=2 to n} (vi*yi)
/* 且，w1*y1 + sum_{i=2 to n} (wi*zi) <= c
/* 进一步有：
/* v1*y1 + sum_{i=2 to n} (vi*zi) > sum_{i=1 to n} (vi*yi)
/* w1*y1 + sum_{i=2 to n} (wi*zi) <= c
/* 这说明：(y1,z2,z3,...zn)是所给0-1背包问题的更优解，那么
/* 说明(y1,y2,...,yn)不是问题的最优解，与前提矛盾，所以最优
/* 子结构性质成立。
/*
/* 2.2 子问题重叠性质
/* 设所给0-1背包问题的子问题 P(i,j)为：
/* max sum_{k=i to n} (vk*xk)
/* (1) sum_{k=i to n} (wk*xk) <= j
/* (2) xk∈{0, 1}, i<=k<=n
/* 问题P(i,j)是背包容量为j、可选物品为i,i+1,...,n时的子问题
/* 设m(i,j)是子问题P(i,j)的最优值，即最大总价值。则根据最优
/* 子结构性质，可以建立m(i,j)的递归式：
/* a. 递归初始 m(n,j)
/* //背包容量为j、可选物品只有n，若背包容量j大于物品n的
/* //重量，则直接装入；否则无法装入。
/* m(n,j) = vn, j>=wn
/* m(n,j) = 0, 0<=j<wn
/* b. 递归式 m(i,j)
/* //背包容量为j、可选物品为i,i+1,...,n
/* //如果背包容量j<wi，则根本装不进物品i，所以有：
/* m(i,j) = m(i+1,j), 0<=j<wi
/* //如果j>=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) < (b)) ? (a) : (b))
template <typename Type>
void Knapsack(Type* v, int *w, int c, int n, Type **m)
{
//递归初始条件
int jMax = min(w[n] - 1, c);
for (int j=0; j<=jMax; j++) {
m[n][j] = 0;
}
for (j=w[n]; j<=c; j++) {
m[n][j] = v[n];
}
//i从2到n-1，分别对j>=wi和0<=j<wi即使m(i,j)
for (int i=n-1; i>1; i--) {
jMax = min(w[i] - 1, c);
for (int j=0; j<=jMax; j++) {
m[i][j] = m[i+1][j];
}
for (j=w[i]; j<=c; j++) {
m[i][j] = max(m[i+1][j], m[i+1][j-w[i]]+v[i]);
}
}
m[1][c] = m[2][c];
if (c >= w[1]) {
m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]);
}
}
template <typename Type>
void TraceBack(Type **m, int *w, int c, int n, int* x)
{
for (int i=1; i<n; i++) {
if(m[i][c] == m[i+1][c]) x[i] = 0;
else {
x[i] = 1;
c -= w[i];
}
}
x[n] = (m[n][c])? 1:0;
}
int main(int argc, char* argv[])
{
int n = 5;
int w[6] = {-1, 2, 2, 6, 5, 4};
int v[6] = {-1, 6, 3, 5, 4, 6};
int c = 10;
int **ppm = new int*[n+1];
for (int i=0; i<n+1; i++) {
ppm[i] = new int[c+1];
}
int x[6];
Knapsack<int>(v, w, c, n, ppm);
TraceBack<int>(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<=M( M=150)
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占空间最小的物品装入是否能得到最优解？
（3）每次选取单位容量价值最大的物品，成为解本题的策略。
<程序代码:>(环境:c++)
#include<iostream.h>
#define max 100 //最多物品数
void sort (int n,float a[max],float b[max]) //按价值密度排序
{
int j,h,k;
float t1,t2,t3,c[max];
for(k=1;k<=n;k++)
c[k]=a[k]/b[k];
for(h=1;h<n;h++)
for(j=1;j<=n-h;j++)
if(c[j]<c[j+1])
{t1=a[j];a[j]=a[j+1];a[j+1]=t1;
t2=b[j];b[j]=b[j+1];b[j+1]=t2;
t3=c[j];c[j]=c[j+1];c[j+1]=t3;
}
}
void knapsack(int n,float limitw,float v[max],float w[max],int x[max])
{float c1; //c1为背包剩余可装载重量
int i;
sort(n,v,w); //物品按价值密度排序
c1=limitw;
for(i=1;i<=n;i++)
{
if(w[i]>c1)break;
x[i]=1; //x[i]为1时，物品i在解中
c1=c1-w[i];
}
}
void main()
{int n,i,x[max];
float v[max],w[max],totalv=0,totalw=0,limitw;
cout<<"请输入n和limitw:";
cin>>n >>limitw;
for(i=1;i<=n;i++)
x[i]=0; //物品选择情况表初始化为0
cout<<"请依次输入物品的价值："<<endl;
for(i=1;i<=n;i++)
cin>>v[i];
cout<<endl;
cout<<"请依次输入物品的重量："<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<endl;
knapsack (n,limitw,v,w,x);
cout<<"the selection is:";
for(i=1;i<=n;i++)
{
cout<<x[i];
if(x[i]==1)
totalw=totalw+w[i];
}
cout<<endl;
cout<<"背包的总重量为："<<totalw<<endl; //背包所装载总重量
cout<<"背包的总价值为："<<totalv<<endl; //背包的总价值
}
三.回溯算法求解0-1背包问题
1.0-l背包问题是子集选取问题。
一般情况下，0-1背包问题是NP难题。0-1背包
问题的解空间可用子集树表示。解0-1背包问题的回溯法与装载问题的回溯法十分类
似。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当
右子树有可能包含最优解时才进入右子树搜索。否则将右子树剪去。设r是当前剩余
物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+r≤bestp时，可剪去右
子树。计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序，然后
依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是
右子树中解的上界。
2.解决办法思路：
为了便于计算上界，可先将物品依其单位重量价值从大到小排序，此后只要顺序考
察各物品即可。在实现时，由bound计算当前结点处的上界。在搜索解空间树时，只要其左儿子节点是一个可行结点，搜索就进入左子树，在右子树中有可能包含最优解是才进入右子树搜索。否则将右子树剪去。
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。
2.算法框架：
a.问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。
b.回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
3.运用回溯法解题通常包含以下三个步骤：
a.针对所给问题，定义问题的解空间；
b.确定易于搜索的解空间结构；
c.以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；
#include<iostream>
using namespace std;
class Knap
{
friend int Knapsack(int p[],int w[],int c,int n );
public:
void print()
{
for(int m=1;m<=n;m++)
{
cout<<bestx[m]<<" ";
}
cout<<endl;
};
private:
int Bound(int i);
void Backtrack(int i);
int c;//背包容量
int n; //物品数
int *w;//物品重量数组
int *p;//物品价值数组
int cw;//当前重量
int cp;//当前价值
int bestp;//当前最优值
int *bestx;//当前最优解
int *x;//当前解
};
int Knap::Bound(int i)
{
//计算上界
int cleft=c-cw;//剩余容量
int b=cp;
//以物品单位重量价值递减序装入物品
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i];
b+=p[i];
i++;
}
//装满背包
if(i<=n)
b+=p[i]/w[i]*cleft;
return b;
}
void Knap::Backtrack(int i)
{
if(i>n)
{
if(bestp<cp)
{
for(int j=1;j<=n;j++)
bestx[j]=x[j];
bestp=cp;
}
return;
}
if(cw+w[i]<=c) //搜索左子树
{
x[i]=1;
cw+=w[i];
cp+=p[i];
Backtrack(i+1);
cw-=w[i];
cp-=p[i];
}
if(Bound(i+1)>bestp)//搜索右子树
{
x[i]=0;
Backtrack(i+1);
}
}
class Object
{
friend int Knapsack(int p[],int w[],int c,int n);
public:
int operator<=(Object a)const
{
return (d>=a.d);
}
private:
int ID;
float d;
};
int Knapsack(int p[],int w[],int c,int n)
{
//为Knap::Backtrack初始化
int W=0;
int P=0;
int i=1;
Object *Q=new Object[n];
for(i=1;i<=n;i++)
{
Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i];
P+=p[i];
W+=w[i];
}
if(W<=c)
return P;//装入所有物品
//依物品单位重量排序
float f;
for( i=0;i<n;i++)
for(int j=i;j<n;j++)
{
if(Q[i].d<Q[j].d)
{
f=Q[i].d;
Q[i].d=Q[j].d;
Q[j].d=f;
}
}
Knap K;
K.p = new int[n+1];
K.w = new int[n+1];
K.x = new int[n+1];
K.bestx = new int[n+1];
K.x[0]=0;
K.bestx[0]=0;
for( i=1;i<=n;i++)
{
K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
}
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
//回溯搜索
K.Backtrack(1);
K.print();
delete [] Q;
delete [] K.w;
delete [] K.p;
return K.bestp;
}
void main()
{
int *p;
int *w;
int c=0;
int n=0;
int i=0;
char k;
cout<<"0-1背包问题——回溯法 "<<endl;
cout<<" by zbqplayer "<<endl;
while(k)
{
cout<<"请输入背包容量(c)："<<endl;
cin>>c;
cout<<"请输入物品的个数(n)："<<endl;
cin>>n;
p=new int[n+1];
w=new int[n+1];
p[0]=0;
w[0]=0;
cout<<"请输入物品的价值(p)："<<endl;
for(i=1;i<=n;i++)
cin>>p[i];
cout<<"请输入物品的重量(w)："<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<"最优解为(bestx)："<<endl;
cout<<"最优值为(bestp)："<<endl;
cout<<Knapsack(p,w,c,n)<<endl;
cout<<"[s] 重新开始"<<endl;
cout<<"[q] 退出"<<endl;
cin>>k;
}
四.分支限界法求解0-1背包问题
1.问题描述：已知有N个物品和一个可以容纳M重量的背包，每种物品I的重量为WEIGHT，一个只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的总效益最大。
2.设计思想与分析：对物品的选取与否构成一棵解树，左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。
#include <iostream.h>
struct good
{
int weight;
int benefit;
int flag;//是否可以装入标记
};
int number=0;//物品数量
int upbound=0;
int curp=0, curw=0;//当前效益值与重量
int maxweight=0;
good *bag=NULL;
void Init_good()
{
bag=new good [number];
for(int i=0; i<number; i++)
{
cout<<"请输入第件"<<i+1<<"物品的重量:";
cin>>bag[i].weight;
cout<<"请输入第件"<<i+1<<"物品的效益:";
cin>>bag[i].benefit;
bag[i].flag=0;//初始标志为不装入背包
cout<<endl;
}
}
int getbound(int num, int *bound_u)//返回本结点的c限界和u限界
{
for(int w=curw, p=curp; num<number && (w+bag[num].weight)<=maxweight; num++)
{
w=w+bag[num].weight;
p=w+bag[num].benefit;
}
*bound_u=p+bag[num].benefit;
return ( p+bag[num].benefit*((maxweight-w)/bag[num].weight) );
}
void LCbag()
{
int bound_u=0, bound_c=0;//当前结点的c限界和u限界
for(int i=0; i<number; i++)//逐层遍历解树决定是否装入各个物品
{
if( ( bound_c=getbound(i+1, &bound_u) )>upbound )//遍历左子树
upbound=bound_u;//更改已有u限界,不更改标志
if( getbound(i, &bound_u)>bound_c )//遍历右子树
//若装入，判断右子树的c限界是否大于左子树根的c限界，是则装入
{
upbound=bound_u;//更改已有u限界
curp=curp+bag[i].benefit;
curw=curw+bag[i].weight;//从已有重量和效益加上新物品
bag[i].flag=1;//标记为装入
}
}
}
void Display()
{
cout<<"可以放入背包的物品的编号为：";
for(int i=0; i<number; i++)
if(bag[i].flag>0)
cout<<i+1<<" ";
cout<<endl;
delete []bag;
}
I. 求C++语言版用回溯法解决八皇后问题的代码
#include <fstream>
#include <bitset>
#include <vector>
using namespace std;
ofstream cout("out.txt");
void BitSetTest()
{
const int n = 4;
for (int i = 0; i < 16; i++)
cout << bitset<4>(i) << endl;
}
class Enum
{
protected:
vector<int> A;
int M, N;
void Print()
{
for (int i = 0; i < N; i++)
cout << A[i];
cout << endl;
}
virtual bool Valid(int k) {return true;}
public:
Enum(int m, int n): M(m), N(n), A(n) {}
void Generate(int k)
{
if (k == N)
Print();
else
for (A[k] = 0; A[k] < M; A[k]++)
if (Valid(k))
Generate(k + 1);
}
void Generate()
{
int k = 0;
A[k] = -1;
while (k >= 0)
{
A[k]++;
if (A[k] == M)
k--;
else if (Valid(k))
{
if (k == N - 1)
Print();
else
A[++k] = -1;
}
}
}
};
class Perm: public Enum
{
virtual bool Valid(int k)
{
bool v = true;
for (int i = 0; v && i < k; i++)
v = A[k] != A[i];
return v;
}
public:
Perm(int n): Enum(n, n) {}
};
class nQueens: public Enum
{
virtual bool Valid(int k)
{
bool v = true;
for (int i = 0; v && i < k; i++)
v = A[k] != A[i] && k - i != abs(A[k] - A[i]);
return v;
}
public:
nQueens(int n): Enum(n, n) {}
};
int main()
{
nQueens(8).Generate();
return 0;
}
J. c++编程问题 回溯算法 请大师帮忙讲解 源代码不要 上课没听懂啊！！
//这题不可用回溯法来解的,因为枚举的空间太大了,有2^30次方呢,这样会挂掉的,应该用DP
//dp[i][j][k]表示的是长度为i的串,以j,k为末尾两位的合法串有多少种. 长度i+1可以从i的加上0或者加上1得到
//dp[i+1][k][p]=sum{dp[i][j][k]}(j!=p&&k!=p)
#include<malloc.h>
#include<stdio.h>
int dp[33][2][2]={0};
int main()
{
int i,j,k,p,n;
dp[1][0][0]=1;
dp[1][0][1]=1;
dp[2][0][0]=1;
dp[2][0][1]=1;
dp[2][1][0]=1;
dp[2][1][1]=1;
for(i=3;i<33;i++)
{
for(j=0;j<2;j++)
{
for(k=0;k<2;k++)
{
for(p=0;p<2;p++)
{
if(j==k&&k==p)continue;
dp[i][k][p]+=dp[i-1][j][k];
}
}
}
}
while(scanf("%d",&n)!=EOF)
{
printf("%d\n",dp[n][0][0]+dp[n][0][1]+dp[n][1][0]+dp[n][1][1]);
}
return 0;
}