假如要去一个地方旅游，计划 N 天时间，每一个景点游玩时间是不同的，每个景点在心中排名也是不同的，那么如何在 N 天时间里安排一个能够得到排名分最高的景点组合

示例：

后续为了程序方便，统一最小游玩时间单位为 1 天

景点	游玩时间	分数
A	1	9
B	4	9
C	2	9
D	1	7
E	1	6
F	2	8
G	1	5

计划天数： N = 6 ，我们先抛出一个表格

	1 DAY	2 DAYs	3 DAY	4 DAYs	5 DAY	6 DAY
A (1,9)	9	9	9	9	9	9
B (4,9)	9	9	9	9	18	18
C (2,9)	9	9	18	18	18	18
D (1,7)	9	16	18	25	25	25
E (1,6)	9	16	22	25	31	31
F (2,8)	9	16	22	25	31	33
G (1,5)	9	16	22	27	31	36

表格解释：

x DAY：总共只有 x 天时间

A (1,9)：A - 景点名；1 - 游玩时间 1 天； 9 - 分数

	1 DAY	2 DAYs	3 DAYs	4 DAYs	5 DAYs	6 DAYs
A (1,9)	9	9	9	9	9	9

只有 A 景点的情况下，只能游玩 A，每一天都一样，所以每一天分数都是 9

	1 DAY	2 DAYs	3 DAYs	4 DAYs	5 DAYs	6 DAYs
A (1,9)	9	9	9	9	9	9
B (4,9)	9	9	9	9	18	18

B 景点来了，由于游玩 B 需要耗时 4 天，所以 1-3 天的时间 只能游玩 A，分数为 9

                     4天 时间整好够 B，那么看看 B 与 A 那个分数高就选那个

                     5天 时间，如果游玩 B，那么剩下 1 天时间，选 A，这样分数是 9+9，比其上一行 9 大，所以这里组合分 18

                      6天 时间，B 4天，剩下 2 天，2天的话查看上一栏 2 天栏位是 9，选择 4天+2天=18 分更大

其余表格同样道理

总结：

当前单元格的值：

1. 当前景点值无法放入，那么取上一行，同列的值

2. 可以放入，比较取较大的值：上一行同列 或 当前景点值+剩余天数代表的最大值（查上一行对应栏位）

代码部分：

由于 C 的局限性，目前版本仅仅计算表格分数，不显示具体组合景点情况

定义结构体，表示景点信息

typedef struct Element {char name[32];int cost;int value;
}Element;

   一维数组存放所有景点

void addTourElements(Element *elements, int eleIdx, char *name, int cost, int value)
{strcpy(elements[eleIdx].name, name);elements[eleIdx].cost = cost;elements[eleIdx].value = value;
}

分数表格由二维数组表示，创建和删除

int ** createMap(int row, int col)
{int i,j;int **map = (int **)malloc(sizeof(int *) * row);for(i=0; i<row; i++){map[i] = (int *)malloc(sizeof(int) * col);}for(i=0; i<row; i++){for(j=0; j<col; j++){map[i][j] = 0;}}return map;
}

void deleteMap(int **map, int row, int col)
{int i;for(i=0; i<row; i++)free(map[i]);free(map);
}

构建分数过程

void caculate(Element *elements, int eleSize)
{int i,j;int curValue = 0;int curCost = 0;int leftValue = 0;int leftCost = 0;int **map = createMap(eleSize, TOURDAYS);for(i=0; i<eleSize; i++) // each element{for(j=0; j<TOURDAYS; j++) // check each day size{if(i == 0) // 1st element fill line one{map[i][j] = elements[i].value;}else{			curValue = elements[i].value;curCost = elements[i].cost;leftCost = j+1-elements[i].cost;//printf("curValue=%d, curCost=%d, leftCost=%d\n", curValue, curCost, leftCost);if(leftCost < 0) // can't cost, use pre value{map[i][j] = map[i-1][j];}else if(leftCost == 0){map[i][j] = max(curValue, map[i-1][j]);}else{leftValue = map[i-1][leftCost-1];//printf("leftValue=%d\n", leftValue);map[i][j] = max(curValue + leftValue, map[i-1][j]);}}}}dispMap(map, eleSize, TOURDAYS);deleteMap(map, eleSize, TOURDAYS);
}

提供一些显示功能

void dispTourElements(Element *elements, int eleSize)
{int i;for(i=0; i<eleSize; i++){printf("Element (%d/%d): ", i+1, eleSize);printf("name=%s ", elements[i].name);printf("cost=%d ", elements[i].cost);printf("value=%d\n", elements[i].value);}printf("\n");
}void dispMap(int **map, int row, int col)
{int i,j,k;printf("1 Day ");for(k=2; k<=TOURDAYS; k++)printf("%2d Days ", k);printf("\n");for(i=0; i<row; i++){for(j=0; j<col; j++){printf(" %-6d ", map[i][j]);}printf("\n");}printf("\n");
}

主函数部分

int main(void)
{int i;int eleSize = 7;Element *elements = (Element *)malloc(sizeof(Element) * eleSize);i = 0;while(i < eleSize){addTourElements(elements, i++, "A", 1, 9);addTourElements(elements, i++, "B", 4, 9);addTourElements(elements, i++, "C", 2, 9);addTourElements(elements, i++, "D", 1, 7);addTourElements(elements, i++, "E", 1, 6);addTourElements(elements, i++, "F", 2, 8);addTourElements(elements, i++, "G", 1, 5);}dispTourElements(elements, eleSize);caculate(elements, eleSize);#if 0 // expected map1 DAY	2 DAYs	3 DAYs	4 DAYs	5 DAYs	6 DAYsA (1,9)	 9		9	    9		9		9		9B (4,9)	 9		9		9		9		18		18	C (2,9)  9		9		18		18		18		18D (1,7)  9		16		18		25		25		25E (1,6)  9		16		22		25		31		31F (2,8)  9		16		22		25		31		33G (1,5)  9		16		22		27		31		36#endifreturn 0;
}

目前版本属于第一版，后续还会有优化

不过动态规划的示例逻辑如上解释，学习过程中可以先从手动画表格来熟悉构建过程

动态规划的具体定义，后续补充

查看更多刷题笔记