【实验内容】
（1）tsp问题：利用动态规划算法编程求解TSP问题，并进行时间复杂性分析。
输入：n个城市,权值，任选一个城市出发；
输出：以表格形式输出结果，并给出向量解和最短路径长度。
（2）01背包问题：利用动态规划算法编程求解0-1背包问题，并进行时间复杂性分析。
输入:n个物品，重量为{w1, w2, … ,wn}、价值为{v1, v2, … ,vn}，容量为C的背包；
输出：表格输出结果，并给出向量解和最优值。
【编译环境】devc++ 5.11
【解题思路】
tsp问题：
1.输入图的结点个数和代价矩阵
2.按顺序生成集合的子集
3.动态规划法依次处理子集
4.对于复杂性
【参考内容】
d[i][j]表示从顶点i经过子集v[j]中的顶点一次且仅一次，最后回到出发点0的路径长度。
【代码分析】
一.TSP问题主要解决三个问题
1.顺序表示集合
头文件
#include <stdio.h>
#include<malloc.h>
#include<stdlib.h>
生成集合的函数
long unsigned int* collect(int max)//max表示元素最大值。
{
//sum表示子集数量
int sum;
//index指向遍历位置
int index = 0;
//indexin指向填表位置
int indexin = 0;
//n用来存储中间量
unsigned int n=0;
//组合结果总个数，不包含全空的情况，故减一
sum = (int)pow(2,max)-1;
long unsigned int* col = (long unsigned int*)malloc(sizeof(int)*sum);
//初始化为二进制1，10，100，1000，10000...
//即集合{1，2}表示为011，集合{3}表示为100，通过固定位上是否为1表示集合中是否含有这个数
for(int i=0;i<max;i++)
{
col[indexin++] = (unsigned int)pow(2,i);
}
while(index<=sum)
{
for(int i=max-1;i>=0;i--)//从高位判断,集合的最高位方便生成下一位
{
n = (unsigned int)pow(2,i);
//判断固定位上是否位1
if((col[index]&n) != 0 )//！=的优先级大于&运算符的优先级所以要加括号
{
if(i==max-1)
{
break;
}
for(int j=i+1;j<max;j++)//j<max表示最高生成的集合元素位max
{
//利用加法表示集合001+010相当于集合{1,2}
col[indexin++] = col[index]+(unsigned int)pow(2,j);
}
break;
}
}
//生成完毕，开始下一次循环
index++;
}
//方便展示生成的集合
/*
for(int i=0;i<sum;i++)//二进制格式输出
{
char s[max+1];
itoa(col[i],s,2);
printf("%s\n",s);
}
*/
return col;
}
展示生成的集合，形式如下
节点个数为5时：
一些解释
2.从集合中去除一个顶点
因为生成集合的函数使用位数表示集合元素是否存在，所以很方便通过与和非操作去除一个顶点
vindex[j]&(~(long unsigned int)pow(2,h-1))
假设vindex[j]为二进制1111即集合{1，2，3，4}
当h为2时，则pow(2,h-1)：10为二进制10即集合{2}
非：1101
再进行与操作：1111与1101->1101即从原集合中去除了元素2。
3.动态规划法依次处理集合和数据
生成数据并初始化第一列数据
头文件和宏定义
#include<time.h>
#include<random>
#define MAX 999//设置最大权值
#define MAXNODE 5//节点数
#define INF 99999//默认最大值
数据初始化
int main() {
int node;
//自动生成方式
//数据写入文件
FILE* fp = fopen("demo.TXT","w");
//生成随机数
srand((unsigned)time(NULL));
node = MAXNODE;
//生成数组矩阵，用一维数组表示二维数组
int *d = (int*)malloc(sizeof(int)*999*999);
for(int i=0;i<node;i++)
{
for(int j=0;j<node;j++)
{
//行列相等默认最大值
if(j == i)
d[i*node+j] = INF;
else
d[i*node+j] = rand()%MAX+1;
fprintf(fp, "%d\t",d[i*node+j]);
fprintf(fp, " ");
}
fprintf(fp, "\n");
}
//关闭文件
fclose(fp);
//调用tsp函数
tsp(d,node);
}
TSP算法实现
算法实现按照参考图片中第二步
//d表示数组矩阵。n表示节点个数（包括0节点）
void tsp(int* d,int n)
{
//数组的索引序号，表示数组处理的顺序
long unsigned int*vindex;
//数组下标代表不同子集，数组存储相应节点对应的最短路径长度
int *v = (int*)malloc(sizeof(int)*n*(int)pow(2,n));
//记录向量解
int vec[n*(int)pow(2,n)+1]={0};
//初始化
for(int i=0;i<n;i++)
{
v[i*(int)pow(2,n)+0] = d[i*n+0];
for(int j=1;j<(int)pow(2,n);j++)
{
v[i*(int)pow(2,n)+j] = INF;
}
}
//vindex存储的就是遍历子集的顺序,n-1表示子集元素最多为n-1个，0作为出发点
vindex = collect(n-1);
//以下算法每一步都是解释算法书上的伪代码
int j=0;
while(j<pow(2,n-1)-1)//依次处理每一个子集数组v[j]
{
if(j==pow(2,n-1)-2)//此时是全集的情况，输出最短路径
{
long unsigned int min=INF;
int m=0;
for(int h=1;h<n;h++)//遍历全集中每一个元素
{
if(min>d[0*n+h]+v[h*(int)pow(2,n)+(vindex[j]&(~(long unsigned int)pow(2,h-1)))])
{
min=d[0*n+h]+v[h*(int)pow(2,n)+(vindex[j]&(~(long unsigned int)pow(2,h-1)))];
vec[0*((int)pow(2,n)+1)+vindex[j]]=h;
}
}
v[0*(int)pow(2,n)+vindex[j]]=min;
break;//跳出循环直接输出
}
//开始处理每一个子集
for(int i=1;i<n;i++)
{
if((vindex[j]&(int)pow(2,i-1))==0)//v[j]中不包含i
{
long unsigned int min=INF;
//对Vindex[j]中每一个元素h，计算v[i][j]=min{d[i][h]+v[h][j-1]}
for(int h=1;h<n;h++)//遍历每一个元素，计算最小路径
{
if((vindex[j]&(long unsigned int)pow(2,h-1))!=0)//判断元素h在vindex[j]中
{
if(min>d[i*n+h]+v[h*(int)pow(2,n)+(vindex[j]&(~(long unsigned int)pow(2,h-1)))])
{
min=d[i*n+h]+v[h*(int)pow(2,n)+(vindex[j]&(~(long unsigned int)pow(2,h-1)))];
vec[i*((int)pow(2,n)+1)+vindex[j]]=h;
}
}
}
v[i*(int)pow(2,n)+vindex[j]]=min;
}
}
j++;
}
//打印表格，向量解，最短路径长度
printout(d,v,vindex,vec,n);
}
输出函数
void printout(int*d,int*v,unsigned long int*vindex,int*vec,int n)
{
//输出表格
printf("\t%-8d",0);
for(int i=0;i<pow(2,n-1)-1;i++)//二进制格式输出
{
char s[n];
itoa(vindex[i],s,2);
printf("%-8s",s);
}
printf("\n");
for(int i=0;i<n;i++)
{
printf("%-8d",i);
if(d[i*n+0]<INF)
printf("%-8d",d[i*n+0]);
else
printf("%-8d",0);
for(int j=0;j<pow(2,n-1)-1;j++)
{
if(v[i*(int)pow(2,n)+vindex[j]]>=INF)
printf("%-8d",0);
else
printf("%-8d",v[i*(int)pow(2,n)+vindex[j]]);
}
printf("\n");
}
//输出向量解
//记录每一层循环里最小的值作为下一个节点
int maxcomb=pow(2,n-1)-2;//减去空集减去全集减去编号从0开始造成的偏移，所以减3
int last;
int nextlast = vec[0*((int)pow(2,n)+1)+vindex[(int)pow(2,n-1)-2]];
int vecindex= vindex[(int)pow(2,n-1)-2];//全集的第一个向量
unsigned long int min;
printf("向量解：<%d->%d> ",0,nextlast);
for(int j=n;j>1;j--)//寻找n次向量解,每个阶段一次
{
if(j==2)
{
printf("<%d->%d> \n",nextlast,0);
break;
}
last = nextlast;
vecindex = (vecindex&(~(long unsigned int)pow(2,last-1)));//集合中删除last
nextlast = vec[last*((int)pow(2,n)+1)+vecindex];
printf("<%d->%d> ",last,nextlast);
}
//输出最短路径长度
printf("最短路径：%ld",v[vindex[(int)pow(2,n-1)-2]]);
}
输出
数据
4.复杂度分析
5.TSP问题源代码
#include <stdio.h>
#include<malloc.h>
#include<time.h>
#include<random>
#include<stdlib.h>
//宏定义区
#define MAX 99//设置最大权值
#define MAXNODE 5//节点数
#define INF 9999//默认最大值
//全局变量区
//函数声明区
void tsp(int*,int);
long unsigned int* collect(int);
void printout(int*,int*,unsigned long int*,int*,int);//数组矩阵,子集值，子集索引，子集向量解，最大元素
int main() {
int node;
//自动生成方式
//数据写入文件
FILE* fp = fopen("demo.TXT","w");
//生成随机数
srand((unsigned)time(NULL));
node = MAXNODE;
//生成数组矩阵，用一维数组表示二维数组
int *d = (int*)malloc(sizeof(int)*999*999);
for(int i=0;i<node;i++)
{
for(int j=0;j<node;j++)
{
//行列相等默认最大值
if(j == i)
d[i*node+j] = INF;
else
d[i*node+j] = rand()%MAX+1;
fprintf(fp, "%d\t",d[i*node+j]);
fprintf(fp, " ");
}
fprintf(fp, "\n");
}
//关闭文件
fclose(fp);
//调用tsp函数
tsp(d,node);
}
long unsigned int* collect(int max)//max表示元素最大值。
{
//sum表示子集数量
int sum;
//index指向遍历位置
int index = 0;
//indexin指向填表位置
int indexin = 0;
//n用来存储中间量
unsigned int n=0;
//组合结果总个数，不包含全空的情况，故减一
sum = (int)pow(2,max)-1;
long unsigned int* col = (long unsigned int*)malloc(sizeof(int)*sum);
//初始化为二进制1，10，100，1000，10000...
//即集合{1，2}表示为011，集合{3}表示为100，通过固定位上是否为1表示集合中是否含有这个数
for(int i=0;i<max;i++)
{
col[indexin++] = (unsigned int)pow(2,i);
}
while(index<=sum)
{
for(int i=max-1;i>=0;i--)//从高位判断,集合的最高位方便生成下一位
{
n = (unsigned int)pow(2,i);
//判断固定位上是否位1
if((col[index]&n) != 0 )//！=的优先级大于&运算符的优先级所以要加括号
{
if(i==max-1)
{
break;
}
for(int j=i+1;j<max;j++)//j<max表示最高生成的集合元素位max
{
//利用加法表示集合001+010相当于集合{1,2}
col[indexin++] = col[index]+(unsigned int)pow(2,j);
}
break;
}
}
//生成完毕，开始下一次循环
index++;
}
//方便展示生成的集合
/*
for(int i=0;i<sum;i++)//二进制格式输出
{
char s[max+1];
itoa(col[i],s,2);
printf("%s\n",s);
}
*/
return col;
}
void printout(int*d,int*v,unsigned long int*vindex,int*vec,int n)
{
//输出表格
printf("\t%-8d",0);
for(int i=0;i<pow(2,n-1)-1;i++)//二进制格式输出
{
char s[n];
itoa(vindex[i],s,2);
printf("%-8s",s);
}
printf("\n");
for(int i=0;i<n;i++)
{
printf("%-8d",i);
if(d[i*n+0]<INF)
printf("%-8d",d[i*n+0]);
else
printf("%-8d",0);
for(int j=0;j<pow(2,n-1)-1;j++)
{
if(v[i*(int)pow(2,n)+vindex[j]]>=INF)
printf("%-8d",0);
else
printf("%-8d",v[i*(int)pow(2,n)+vindex[j]]);
}
printf("\n");
}
//输出向量解
//记录每一层循环里最小的值作为下一个节点
int maxcomb=pow(2,n-1)-2;//减去空集减去全集减去编号从0开始造成的偏移，所以减3
int last;
int nextlast = vec[0*((int)pow(2,n)+1)+vindex[(int)pow(2,n-1)-2]];
int vecindex= vindex[(int)pow(2,n-1)-2];//全集的第一个向量
unsigned long int min;
printf("向量解：<%d->%d> ",0,nextlast);
for(int j=n;j>1;j--)//寻找n次向量解,每个阶段一次
{
if(j==2)
{
printf("<%d->%d> \n",nextlast,0);
break;
}
last = nextlast;
vecindex = (vecindex&(~(long unsigned int)pow(2,last-1)));//集合中删除last
nextlast = vec[last*((int)pow(2,n)+1)+vecindex];
printf("<%d->%d> ",last,nextlast);
}
//输出最短路径长度
printf("最短路径：%ld",v[vindex[(int)pow(2,n-1)-2]]);
}
//d表示数组矩阵。n表示节点个数（包括0节点）
void tsp(int* d,int n)
{
//数组的索引序号，表示数组处理的顺序
long unsigned int*vindex;
//数组下标代表不同子集，数组存储相应节点对应的最短路径长度
int *v = (int*)malloc(sizeof(int)*n*(int)pow(2,n));
//记录向量解
int vec[n*(int)pow(2,n)+1]={0};
//初始化
for(int i=0;i<n;i++)
{
v[i*(int)pow(2,n)+0] = d[i*n+0];
for(int j=1;j<(int)pow(2,n);j++)
{
v[i*(int)pow(2,n)+j] = INF;
}
}
//vindex存储的就是遍历子集的顺序,n-1表示子集元素最多为n-1个，0作为出发点
vindex = collect(n-1);
//以下算法每一步都是解释算法书上的伪代码，vec数组用于后面方便输出
int j=0;
while(j<pow(2,n-1)-1)//依次处理每一个子集数组v[j]
{
if(j==pow(2,n-1)-2)//此时是全集的情况，输出最短路径
{
long unsigned int min=INF;
int m=0;
for(int h=1;h<n;h++)//遍历全集中每一个元素
{
if(min>d[0*n+h]+v[h*(int)pow(2,n)+(vindex[j]&(~(long unsigned int)pow(2,h-1)))])
{
min=d[0*n+h]+v[h*(int)pow(2,n)+(vindex[j]&(~(long unsigned int)pow(2,h-1)))];
vec[0*((int)pow(2,n)+1)+vindex[j]]=h;
}
}
v[0*(int)pow(2,n)+vindex[j]]=min;
break;//跳出循环直接输出
}
//开始处理每一个子集
for(int i=1;i<n;i++)
{
if((vindex[j]&(int)pow(2,i-1))==0)//v[j]中不包含i
{
long unsigned int min=INF;
//对Vindex[j]中每一个元素h，计算v[i][j]=min{d[i][h]+v[h][j-1]}
for(int h=1;h<n;h++)//遍历每一个元素，计算最小路径
{
if((vindex[j]&(long unsigned int)pow(2,h-1))!=0)//判断元素h在vindex[j]中
{
if(min>d[i*n+h]+v[h*(int)pow(2,n)+(vindex[j]&(~(long unsigned int)pow(2,h-1)))])
{
min=d[i*n+h]+v[h*(int)pow(2,n)+(vindex[j]&(~(long unsigned int)pow(2,h-1)))];
vec[i*((int)pow(2,n)+1)+vindex[j]]=h;
}
}
}
v[i*(int)pow(2,n)+vindex[j]]=min;
}
}
j++;
}
//打印表格，向量解，最短路径长度
printout(d,v,vindex,vec,n);
}
二.01背包问题
【解题思路】
1.获取背包容量packvol，物品数量n，物品价值和重量value[],weigth[]
2.动态规划法求解01背包问题
3.对于复杂性
【参考内容】
背包最大价值
装入背包的物品
【代码分析】
1.动态规划法求解背包最大价值
初始化
//价值矩阵
int v[n+1][packvol+1]={0};
//背包是否装入物品
int x[n+1];
//初始化第0行和第0列
for(int i=0;i<=packvol;i++)
{
v[0][i]=0;
}
for(int i=0;i<=n;i++)
{
v[i][0]=0;
x[i]=0;
}
动态规划法遍历价值矩阵
//依次遍历数组
for(int i=1;i<=n;i++)//物品
{
for(int j=1;j<=packvol;j++)//背包容量
{
if(weight[i-1]>j)//装不下
v[i][j]=v[i-1][j];
if(weight[i-1]<=j)//装的下，继续判断是否最优
{
v[i][j] = v[i-1][j-weight[i-1]]+value[i-1]>v[i-1][j]?v[i-1][j-weight[i-1]]+value[i-1]:v[i-1][j];
}
}
}
2.按要求输出
表格
//输出表格
for(int i=0;i<=n;i++)
{
for(int j=0;j<=packvol;j++)
{
printf("%-4d",v[i][j]);//左对齐输出
}
printf("\n");
}
向量解
//向量解
printf("向量解{行，列}：");
for(int i=n,j=packvol;i>0;i--)
{
printf("{%d,%d}->",i,j);
if(v[i][j]>v[i-1][j])
{
x[i]=1;//参考内容第三个图片
j= j-weight[i-1];
}
if(i==1)
{
printf("{%d,%d}",i-1,j);
}
}
最优解和最大价值
//最优解
printf("\n最优解：");
for(int i=1;i<=n;i++)
{
printf("%d",x[i]);
}
printf("\n最大价值：%d",v[n][packvol]);
输出
数据
文章来源：https://www.toymoban.com/news/detail-438938.html
3.复杂度分析
文章来源地址https://www.toymoban.com/news/detail-438938.html
4.01背包问题源代码
#include<stdio.h>
#include<time.h>
#include<random>
//宏定义区
#define MAX 60//背包最大容量
#define MAXN 30//最大物品数
#define MAXW 7//物品最大重量
#define MAXV 7//物品最大价值
//全局变量区
//自定义函数区
void randomint(int,int,int*,int*);
void fwritein(int,int,int*,int*);
void Pack(int,int,int*,int*);
int main()
{
int n,packvol;
srand(time(NULL));
n = rand()%MAXN;
packvol = rand()%MAX+1;
int w[n],v[n];
randomint(packvol,n,w,v);
Pack(n,packvol,w,v);
return 0;
}
void fwritein(int packvol,int n,int* weight,int* value)
{
FILE* fp = fopen("demo2-2.TXT","w");
fprintf(fp,"背包容量：%d\n",packvol);
fprintf(fp,"物品数量：%d\n",n);
for(int i=0;i<n;i++)
{
fprintf(fp,"%d\t%d\t%d\n",i,weight[i],value[i]);
}
fclose(fp);
}
void randomint(int packvol,int n,int* weight,int* value)
{
for(int i=0;i<n;i++)
{
weight[i]=rand()%MAXW+1;
value[i]=rand()%MAXV+1;
}
fwritein(packvol,n,weight,value);
return;
}
void Pack(int n,int packvol,int* weight,int* value)
{
int v[n+1][packvol+1]={0};
int x[n+1];
for(int i=0;i<=packvol;i++)
{
v[0][i]=0;
}
for(int i=0;i<=n;i++)
{
v[i][0]=0;
x[i]=0;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=packvol;j++)
{
if(weight[i-1]>j)
v[i][j]=v[i-1][j];
if(weight[i-1]<=j)
{
v[i][j] = v[i-1][j-weight[i-1]]+value[i-1]>v[i-1][j]?v[i-1][j-weight[i-1]]+value[i-1]:v[i-1][j];
}
}
}
for(int i=0;i<=n;i++)
{
for(int j=0;j<=packvol;j++)
{
printf("%-4d",v[i][j]);
}
printf("\n");
}
printf("向量解{行，列}：");
for(int i=n,j=packvol;i>0;i--)
{
printf("{%d,%d}->",i,j);
if(v[i][j]>v[i-1][j])
{
x[i]=1;
j= j-weight[i-1];
}
if(i==1)
{
printf("{%d,%d}",i-1,j);
}
}
printf("\n最优解：");
for(int i=1;i<=n;i++)
{
printf("%d",x[i]);
}
printf("\n最大价值：%d",v[n][packvol]);
}
到了这里，关于算法设计与分析实验二：动态规划法求解TSP问题和01背包问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
