简介
一个考察动态规划的机试题的数学模型建立，和两种思路的取舍题目
公司分月饼，m个员工，买了n个月饼，m <= n，每个员工至少分一个月饼，但是也可以分到多个，单人分到最多月饼的个数是Max1，单人分到第二多月饼个数是Max2。但需要满足Max1-Max2 <= 3，单人分到第n-1多月饼个数是Max(n-1)，单人分到第n多月饼个数是Max(n), 想要满足Max(n-1) - Max(n) <= 3，问有多少种分月饼的方法？
输入描述：
每一行输入m，n，表示m个员工，n个月饼，m <=n
输出描述：
输出有多少种分法
示例1：
输入
2 4
输出
2
说明
4=1+3
4=2+2
注意：1+3和3+1要算成同一种分法
示例2：
输入
3 5
输出
2
说明
5=1+1+3
5=1+2+3
示例3：
输入
3 12
输出
6
说明
满足要求的6种分法：
1、12 = 1 + 1 + 10 （Max1=10， Max2=1，不满足Max1-Max2 <= 3的约束）
2、12 = 1 + 2 + 9 （Max1=9，Max2=2，不满足Max1-Max2 <= 3的约束）
3、12 = 1 + 3 + 8 （Max1=8，Max2=3，不满足Max1-Max2 <= 3的约束）
4、12 = 1 + 4 + 7 （Max1=7，Max2=4，Max3=1， 满足要求）
5、12 = 1 + 5 + 6 （Max1=6，Max2=5，Max3=1， 不满足要求）
6、12 = 2 + 2 + 8 （Max1=8，Max2=2，不满足要求）
7、12 = 2 + 3 + 7 （Max1=7，Max2=3，不满足要求）
8、12 = 2 + 4 + 6 （Max1=6，Max2=4，Max3=2， 满足要求）
9、12 = 2 + 5 + 5 （Max1=5，Max2=2 满足要求）
10、12 = 3 + 3 + 6 （Max1=6，Max2=3 满足要求）
11、12 = 3 + 4 + 5 （Max1=5，Max2=4，Max3=3 满足要求）
12 = 4 + 4 + 4 （Max1=4，满足要求）
————————————————版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/qq_45763343/article/details/135894692
一、问题分析
首先读题，仔细看描述中的内容，发现需求是
1.公司分月饼，m个员工，买了n个月饼，m<=n，
2.每个员工至少分一个月饼，但是也可以分到多个，
3.单人分到最多月饼的个数是Max1，单人分到第二多月饼个数是Max2。
4.但需要满足Max1 - Max2 <= 3，单人分到第n - 1多月饼个数是Max(n - 1),
5.单人分到第n多月饼个数是Max(n),想要满足Max(n - 1) - Max(n) <= 3，问有多少种月饼的分法
6.输入描述：第一行输入m，n，表示m个员工，n个月饼，m<=n
7.输出描述：输出有多少种分法
二、解题思路
1.首先员工的数量小于等于月饼的数量，所以不用担心有人分不到
2.Max(n-1)-Max(n) <= 3证明员工之间不能存在发月饼数量差超过3个的情况
比如有一个人分到4个月饼，如果其他人最少分到的月饼是8个的话，这种分法不成立
3.我们看一下例子再理解一下问题
比如有2个员工，4块月饼的时候
因为最少每个人分一个月饼，然后说明中的分法是没有剩下的月饼的，月饼要全部分完
所以我们相当于2个人分2块月饼
分法是两个人一人一块或者一个人拿两块，一共两种分法（1+3和3+1算一种分法—，就是说一个人拿三块一个人拿一块和一个人拿一块一个人拿三块我们不做区分）
4.再看一下示例2：
3个员工，5块月饼
因为每个人至少分一块，所以相当于3个人分2块
方法是一个人一块一个人一块，一个人没有
或者一个人两块，两个人没有
一共两种方法
5.再看一下示例3：
3个员工，12块月饼
每个人分至少一块，还剩下9块
3个人分9块
分法是一个人1块一个人1块一个人7块（不成立）
或者一个人1块一个人2块一个人6块（不成立）
或者一个人1块一个人3块一个人5块（成立）
或者一个人1块一个人4块一个人4块（成立）
或者一个人2块一个人3块一个人4块（成立）
或者一个人0块，一个人3块一个人6块（成立）
或者一个人2块，一个人2块一个人5块（成立）
或者一个人3块，一个人3块一个人3块（成立）
6.首先定义两个结构体，Allocation和AllocationList
Allocation结构体用于表示一种月饼的分配方案，其中values是一个动态分配的整数数组指针，用于存储每个员工分到的月饼数量，size表示该分配方案中员工的数量（也就是values的长度）。
typedef struct Allocation {
int* values;
int size;
} Allocation;
AllocationList结构体用于存储所有的分配方案，它包含一个Allocation类型的指针allocations，指向存储所有分配方案的数组，count表示当前已经存储的分配方案的数量，capacity表示allocations数组的容量（即最多能存储多少种分配方案），通过这种方式可以方便地对分配方案列表进行动态管理，当分配方案数量超过容量时进行动态扩展。
typedef struct AllocationList {
Allocation* allocations;
int count;
int capacity;
} AllocationList;
7.然后我们声明一个函数用于初始化分配方案列表，首先为结构体本身分配内存，然后初始化count为0，表示初始时没有存储任何分配方案，设定一个初始的capacity（这里设置为10，可根据实际需求调整），接着为allocations指针分配内存，用于存储具体的分配方案数组，最后返回创建好的列表结构体指针。
AllocationList* createAllocationList() {
AllocationList* list = (AllocationList*)malloc(sizeof(AllocationList));
if(list == NULL) {
perror("内存分配失败");
exit(1);
}
list->count = 0;
list->capacity = 10;
list->allocations = (Allocation*)malloc(list->capacity * sizeof(Allocation));
if(list->allocations == NULL) {
perror("内存分配失败");
free(list);
exit(1);
}
return list;
}
8.然后我们声明一个addAllocation函数用于向已有的分配方案列表中添加一种新的分配方案。添加之前，先检查分配方案的数量count是否已经达到了列表的容量capacity，如果达到了，就动态扩展列表的容量（通过重新分配更大内存空间，将原有数据复制过去的方式），然后将新的分配方案添加到allocations数组中，并将count加1，表示列表中又多了一种分配方式。
void addAllocation(AllocationList* list, Allocation allocation) {
if(list->count >= list->capacity) {
// 如果容量不够，动态扩展容量
int new_capacity = list->capacity * 2;
Allocation* new_allocations = (Allocation*)malloc(new_capacity * sizeof(Allocation));
if(new_allocations == NULL) {
perror("内存分配失败");
exit(1);
}
for(int i = 0; i < list->count; i++) {
new_allocations[i] = list->allocations[i];
}
free(list->allocations);
list->allocations = new_allocations;
list->capacity = new_capacity;
}
list->allocations[list->count++] = allocation;
}
9.然后我们声明一个函数用于释放整个分配方案列表所占用的内存，它首先遍历allocations数组中每个Allocation结构体中的values指针所指向的动态分配的整数数组内存（因为每个分配方案中的员工分到的月饼数数组是动态分配的，需要单独释放），然后释放allocations数组本身的内存以及AllocationList结构体的内存，确保没有内存泄露。
void freeAllocationList(AllocationList* list) {
for(int i = 0; i < list->count; i++) {
free(list->allocations[i].values);
}
free(list->allocations);
free(list);
}
10.之后我们声明递归辅助函数，用于计算月饼的分配方案并将满足条件的方案添加到结果列表中。需要的参数有剩余月饼数量n，总员工数m，上一个员工分到的月饼数last，当前每个员工分配到的月饼数量数组current,当前分配方案的员工数量current_size,结果列表result
void partitionHelper(int n, int m, int last, int* current, int current_size, AllocationList* result) {
首先判断当前分配方案的员工数量current_size是否已经达到了总员工数m，如果达到了，并且剩余月饼数n也刚好为0，说明找到了一种满足条件的分配方案，此时创建一个新的Allocation结构体，为其values数组分配内存，将当前分配方案中每个员工分到的月饼数（存储在current数组中）复制到values数组中，设置size为m，然后通过addAllocation函数将这个新的分配方案添加到结果列表result中。
if(current_size == m) {
if(n == 0) {
Allocation allocation;
allocation.values = (int*)malloc(m * sizeof(int));
if(allocation.values == NULL) {
perror("内存分配失败");
exit(1);
}
for(int i = 0; i < m; i++) {
allocation.values[i] = current[i];
}
allocation.size = m;
addAllocation(result, allocation);
}
return;
}
接着计算当前员工可以分配到的月饼数的范围，start表示起始值，如果当前是第一个员工（current_size == 0),则从0开始，否则取上一个员工分到的月饼数（current[current_size - 1])和0中的较大值作为起始值，保证满足每人至少1个月饼且相邻差值不超过3的条件；end表示结束值，如果当前是第一个员工，则最多可以分到n/m个月饼（平均分配的大致上限），否则取剩余月饼数n和last + 3（last是上一个员工分到的月饼数，要保证差值不超过3）中的较小值作为结束值。
int start = current_size == 0 ? 0 : (current[current_size - 1] > 0 ? current[current_size - 1] : 0);
int end = current_size == 0 ? n / m : (n < last + 3 ? n : last + 3);
最后通过for循环从start到end的每个可能的月饼数i，将其分配给当前员工（存储在current[current_size]中），然后递归调用partitionHelper函数，更新剩余月饼数为n - i，继续计算下一个员工的分配情况，这样通过递归不断地探索所有可能的分配方案并添加到结果列表中。
for(int i = start; i <= end; i++) {
current[current_size] = i;
partitionHelper(n - i, m , i, current, current_size + 1, result);
}
}
11.然后是partition函数，parition函数作为对外的接口函数，首先调用createAllocationList函数创建一个空的分配方案结果列表result，然后为存储当前正在构建的分配方案的数组current分配内存，接着调用partitionHelper函数开始递归计算分配方案，将计算得到的满足条件的方案添加到result列表中，计算完成后释放current数组的内存，最后返回包含所有分配方案的结果列表result.
AllocationList* partition(int n, int m) {
AllocationList* result = createAllocationList();
int* current = (int*)malloc(m * sizeof(int));
if(current == NULL) {
perror("内存分配失败");
exit(1);
}
partitionHelper(n - m, m, 0, current, 0, result);
free(current);
return result;
}
12.然后是主函数，首先定义了月饼总数n和员工数m，然后读取数据，然后调用partition函数计算分配方案列表，输出分配方案的数量以及每个具体的分配方案内容（或者不输出），最后通过freeAllocationList函数释放结果列表所占用的内存，确保程序没有内存泄露，结束整个程序。
int main() {
int n, m;
scanf("%d %d", &m, &n);
AllocationList* result = partition(n, m);
printf("%d\n", result->count);
freeAllocationList(result);
return 0;
}
三、具体步骤
使用的语言是C
#include <stdio.h>
#include <stdlib.h>
// 结构体用于存储一种分配方案
typedef struct Allocation {
int* values;
int size;
} Allocation;
// 结构体用于存储所有分配方案的列表
typedef struct AllocationList {
Allocation* allocations;
int count;
int capacity;
} AllocationList;
// 初始化分配方案列表
AllocationList* createAllocationList() {
AllocationList* list = (AllocationList*)malloc(sizeof(AllocationList));
if (list == NULL) {
perror("内存分配失败");
exit(1);
}
list->count = 0;
list->capacity = 10; // 初始容量，可以根据需要调整
list->allocations = (Allocation*)malloc(list->capacity * sizeof(Allocation));
if (list->allocations == NULL) {
perror("内存分配失败");
free(list);
exit(1);
}
return list;
}
// 向分配方案列表中添加一种分配方案
void addAllocation(AllocationList* list, Allocation allocation) {
if (list->count >= list->capacity) {
// 如果容量不够，动态扩展容量
int new_capacity = list->capacity * 2;
Allocation* new_allocations = (Allocation*)malloc(new_capacity * sizeof(
Allocation));
if (new_allocations == NULL) {
perror("内存分配失败");
exit(1);
}
for (int i = 0; i < list->count; i++) {
new_allocations[i] = list->allocations[i];
}
free(list->allocations);
list->allocations = new_allocations;
list->capacity = new_capacity;
}
list->allocations[list->count++] = allocation;
}
// 释放分配方案列表占用的内存
void freeAllocationList(AllocationList* list) {
for (int i = 0; i < list->count; i++) {
free(list->allocations[i].values);
}
free(list->allocations);
free(list);
}
// 辅助函数，用于递归地计算分配方案
void partitionHelper(int n, int m, int last, int* current, int current_size,
AllocationList* result) {
if (current_size == m) {
if (n == 0) {
Allocation allocation;
allocation.values = (int*)malloc(m * sizeof(int));
if (allocation.values == NULL) {
perror("内存分配失败");
exit(1);
}
for (int i = 0; i < m; i++) {
allocation.values[i] = current[i];
}
allocation.size = m;
addAllocation(result, allocation);
}
return;
}
int start = current_size == 0 ? 0 : (current[current_size - 1] > 0 ?
current[current_size - 1] : 0);
int end = current_size == 0 ? n / m : (n < last + 3 ? n : last + 3);
for (int i = start; i <= end; i++) {
current[current_size] = i;
partitionHelper(n - i, m, i, current, current_size + 1, result);
}
}
// 主函数，用于启动分配方案的计算并返回结果列表
AllocationList* partition(int n, int m) {
AllocationList* result = createAllocationList();
int* current = (int*)malloc(m * sizeof(int));
if (current == NULL) {
perror("内存分配失败");
exit(1);
}
partitionHelper(n - m, m, 0, current, 0, result);
free(current);
return result;
}
int main() {
int m, n;
scanf("%d", &m);
scanf("%d", &n);
AllocationList* result = partition(n, m);
printf("%d\n", result->count);
// for (int i = 0; i < result->count; i++) {
// for (int j = 0; j < result->allocations[i].size; j++) {
// printf("%d ", result->allocations[i].values[j]);
// }
// printf("\n");
// }
freeAllocationList(result);
return 0;