求最短路径的动态规划实现源代码，用C语言在tc2.0中能运行。
希望下面的能对你有所帮助.
我只给出向前处理的代码,
向后处理的你自己改吧,
不然就变成我帮你做作业了.
你可以从递归式”tmp
=
w+GetBestpathF(g,
i,
s,
n,
path);”中看出递推式.
函数名:
GetBestpathF()
参数说明:
g
-Graph
,多段图对象
t
-int,源点
s
-int,汇点
n
-int,总结点个数
path
-Vertex
*,
记录中间路径
函数说明:
后向处理.
函数返回多段图最短路径,
并记录出最短路径的中间结点.
float
GetBestpathF(Graph
g,
int
t,
int
s,
int
n,
Vertex
*path)
{
float
tmp
=
MaxValue;
float
cost
=
MaxValue;
if
(t==s)
return
0;
else{
for
(int
i=0;
ig.NumOfVertices();
i++){
float
w
=
g.GetWeight(t,
i);
if
(w!=0
w!=MaxValue){
//t点到i点的路径存在
tmp
=
w+GetBestpathF(g,
i,
s,
n,
path);
//t的下一个点i到汇点s的最优路径值
if
(tmpcost){
cost
=
tmp;
AddtoPath(t,
i,
path);
}
}
}
}
return
cost;
}
如何用c语言编程实现动态规划？
动态规划主要是 状态 状态转移方程 如果转移方程写出来了 程序就自然出来啦
对于这题 dp[i][j] 表示 走到格子 (i,j) 时 的总和最大值 val[i][j] 表示格子 (i, j) 的值
那么有 dp[i][j] = max( dp[i-1][j] , dp[i][j-1]) + val[i][j];
当然 边界的时候要特殊考虑一下
for(int i = 1; i = m ; i++)
for(int j = 1; j = n; j++)
{
if( i == 1 ) ….;
else if( j == 1 ) ….;
else dp[i][j] = max( dp[i-1][j] , dp[i][j-1]) + val[i][j];
}
最后 dp[m][n] 就是答案啦 ^ ^
c语言用动态规划法的思想输出斐波那契数列前20项。（利用数组）
好像线性规划是不用数组的 我把递归，线性规划和数组的3中方法都贴在这里了。
#include “stdio.h”
#include “stdlib.h”
void Fibonacci(int a[],int n)//循环数组
{
int i=0;
a[0]=1;
a[1]=1;
for(i=2;in;i++)
{
a[i]=a[i-1]+a[i-2];
}
}
int f(int n)//递归
{
if(n==1||n==2) return 1;
return f(n-1)+f(n-2);
}
int f2(int n)//线性规划
{
int f1=1,f2=1,sum=0;
printf(“\n1\n1\n”);
for(int i=3;i=n;i++)
{
sum=f1+f2;
f1=f2;
f2=sum;
printf(“%d \n”,sum);
}
}
void printArray(int a[],int n)
{
int i=0;
for(i=0;in;i++)
{
printf(“%2d “,a[i]);
}
printf(“\n”);
}
main()
{
int a[20],n=0;
Fibonacci(a,20);
printf(“Fibonacci数列如下：\n”);
printArray(a,20);
printf(“请输入n:”);
scanf(“%d”,n);
printf(“%d\n”,f(n));
printf(“线性规划如下:\n”);
f2(n);
system(“pause”);
}
楼主好运！DevC++平台测试通过！
C语言，算法、动态规划：有一个箱子的容量为v（正整数，0
#includestdio.h
#define N 30
int xiangzi(int n ,int V ,int a[]) //楼主后面的Vo数组必须放进递归函数里面或定义成全局数组 另外h[n]什么情况？？
{
int minv,t,m=V;
if(n==0)
{
if(a[n]=V) // V是剩余空间。minv是所生最小空间，是待求变量，而不是已知的 ，不能Vminv 这样用来判断。
minv=V-a[n];
else
minv=V;
}
else
{
t=xiangzi(n-1,V,a);
if(a[n]=V) //可能a[n]比V大 如果按楼主的程序没判断 那么此时m必定小于0，最后的minv肯定是会小雨0的。应该先判断 排除这种情矿。因此前面定义m的时候可以初始化m=V;
m=xiangzi(n-1,V-a[n],a); /*考虑选择这个物体的情况*/
if(tm)
minv=t;
else
minv=m;
}
return minv;
}
void main()
{
int V;
int n,i,m,min;
int Vo[N];
printf(“箱子的容量V为：”);
scanf(“%d”,V);
printf(“物品的种类数为：”);
scanf(“%d”,n);
printf(“物品的体积分别为：\n”);
for(i=0;in;i++)
scanf(“%d”,Vo[i]); //”%d “改成“%d” d后面的空格去掉。不好意思 我学的c++，c的语法不怎么东， 只是调试出来了，不知道原因，可能语法问题吧。
min=xiangzi(n-1,V,Vo);
printf(“%d\n”,min); //另外别忘了输出
system(“pause”);
}
就这样了。。。
C语言-动态规划
#include stdio.h
#include stdlib.h
struct tree {
int value;
struct tree *left;
struct tree *right;
};
#define min(x, y) x y ? x : y
int a[3][3] = {10, 9, 14, 9, 12, 10, 6, 5, 8};
void add_tree_node(struct tree **node, int x, int y, int depth)
{
//printf(“x = %d, y = %d, value = %d, depth = %d\n”, x, y, a[x][y], depth);
*node = (struct tree *)malloc(sizeof(struct tree));
((struct tree *)*node)-value = a[x][y] + a[x][x];
if(depth == 1) {
((struct tree *)*node)-left = ((struct tree *)*node)-right = NULL;
return;
} else {
add_tree_node((((struct tree *)*node)-left), y, (y+1)%3, depth-1);
add_tree_node((((struct tree *)*node)-right), y, (y+2)%3, depth-1);
}
depth–;
}
void print_tree(struct tree *t)
{
if(t == NULL)
return;
printf(“%d “, t-value);
print_tree(t-left);
print_tree(t-right);
}
void free_tree(struct tree *t)
{
if(t == NULL)
return;
free_tree(t-left);
free_tree(t-right);
free(t);
}
int get_short_time(struct tree *t)
{
if(t-left == NULL || t-right == NULL)
return t-value;
return(min(get_short_time(t-left), get_short_time(t-right))+t-value);
}
void main()
{
struct tree *root;
int i, j, minx=0, miny=1;
for(i = 0; i 3; i++)
for(j = 0; j 3; j++)
if(i != j a[minx][miny] a[i][j])
minx = i, miny = j;
printf(“拆卸时间最短的是从第%d套仪器换为第%d套仪器，时间为%d\n”, minx+1, miny+1, a[minx][miny]);
// 创建深度为5的二叉树，将做5次试验的全部可能路径都放到二叉树中
add_tree_node(root, minx, miny, 5);
print_tree(root);
printf(“\n”);
printf(“最短可以完成全部实验的时间是：%d\n”, get_short_time(root));
free_tree(root);
}
微信扫一扫 
支付宝扫一扫 
