Question

C语言-动态规划

某个化学实验室可用三套不同的仪器中任意一套去完成.
在做完一次实验之后,如果下次仍用原用的那套仪器,则必须对仪器的某部分进行清洗,这要花费一段时间;如果下次换用另一套仪器,则要把原仪器从辅助装置上拆卸下来再装上换用的仪器,这也要花费一段时间.假定一次实验的时间比任一套仪器的清洗时间都长,寻么一套仪器换下来后可以在实验过程中清洗,在下次实验时再使用,相当于节省了清洗时间,设当 i != j 时,t[i][j]表示仪器 i 换成仪器 j 时所需的时间; 当 i == j 时,t[i][j]表示i清洗所需的时间.t[i][j]如下表所示.
10 9 14
9 12 10
6 5 8
现在要做5次实验,应如何安排使用仪器的顺序,使得在第一次开始实验之后,到最后一个实验完成之前,花费在仪器清洗和仪器更换上的总时间最少.
如何用动态规划的算法写出一个C程序

Answer 1

#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);
}

追问

能不能不用什么二叉树写程序，不懂

追答

int dynamic_programming(int x, int y, int depth)
{
int t1, t2;
printf("%d ", a[x][y]+a[x][x]);

if(depth == 1)
return a[x][y]+a[x][x];

t1 = get_result(y, (y+1)%3, depth-1);
t2 = get_result(y, (y+2)%3, depth-1);
if(t1 < t2)
return t1 + a[y][(y+1)%3] + a[y][y];
else
return t2 + a[y][(y+2)%3] + a[y][y];
}

main()函数详细实现略，主要是贴上来就报错，保留原来main函数中计算minx，miny部分的代码，然后直接调用：
t = dynamic(minx, miny, 5);
返回结果t就是最少时间的值。