今天要交运筹学动态规划部分的作业，我看了看书，发现有个问题能写出一个不错的程序来，于是心血来潮编程搞了下，效果还不错，嘿嘿，怀念高中时候的动态规划啊~~~
题目是这样的：
有4个工人，要分别指派他们完成4项工作，每人做各项工作的时间如下表：
A B C D
甲 15 18 21 24
乙 19 23 22 18
丙 26 17 16 19
丁 19 21 23 17
问指派哪人去做什么工作，可使总的消耗时间最小？
我的代码如下：
#include <stdio.h> #include <math.h> int p[4]={1,2,4,8}; int rec[6][16],way[6][16]; int map[4][4]={{15,18,21,24},{19,23,22,18},{26,17,16,19},{19,21,23,17}}; int f(int a,int state) { if (a==5 && state==15) return 0; int i; for (i=0;i<4;i++) if ( ((p[i]&state)!=p[i]) && (f(a+1,state|p[i])+map[a-1][i])<rec[a][state] ){ rec[a][state]=f(a+1,state|p[i])+map[a-1][i]; way[a][state]=state|p[i]; } return rec[a][state]; } int func(int a) { int i; for (i=0;i<4;i++) if (a==p[i]) return i+1; } void out(int a,int state) { if (a==5) return; printf("第%d个人做第%d项工作/n",a,func(way[a][state]^state)); out(a+1,way[a][state]); } int main(void) { freopen("123.out","w",stdout); int i,j; for (i=0;i<6;i++) for (j=0;j<16;j++) rec[i][j]=0x7fffffff; printf("最小消耗时间：%d/n",f(1,0)); printf("方案如下：/n"); out(1,0); return 0; }
其中，
f(a,state)表示前a个人，当前状态为state的时候的最小耗费时间。
state是一个2进制的数，大小是从0000-1111，当state从低到高第i位的数为0，就表示之前第i项工作没有安排人做，为1表示做了。
way是一个记录转移状态的数组，用于递归输出方案。
