简介
一个考察动态规划的机试题的数学模型建立，和两种思路的取舍
题目
公司分月饼，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，满足要求）
平台场景
牛客网 可以选择使用多种语言 我选择Java写的
大多数题目需要做输入输出训练
但是这题不用 给定了 形参 m员工 n月饼 最后return方案数量即可
数学模型
把正整数n分为m份自然数，m <= n，排序后，任意相邻数相差不超过3
方案1-动态规划
思路代码
* 这是动态规划方案 * 定义状态 dp[i][j][k] 表示前 i 个人分配了 j 个月饼，且第 i 个人分配了 k 个月饼的方案数。 * 状态方程为 dp[i][j]=∑k=1>>3 dp[i−1][j−k] * 时空复杂度都是 m*n*n*n
public static int countWays(int m, int n) {
int[][][] dp = new int[m + 1][n + 1][n + 1];
// 初始化
for (int k = 1; k <= n ; k++) {
dp[1][k][k] = 1; // 只有1个员工时，只有一种分法
}
// 动态规划
for (int i = 1; i <= m; i++) {
for (int j = i; j <= n; j++) { // 确保月饼数量不少于员工数
for (int k = 1; k <= j; k++) { // 每个员工至少分得1个月饼
for (int l = 1; l <= k; l++) { // 确保当前分配不超过上一个员工的分配
dp[i][j][k] += dp[i - 1][j - k][l];
}
}
}
}
// 汇总结果
int count = 0;
for (int k = 0; k <= n; k++) {
System.out.println("dp" + m + n + k + " " + dp[m][n][k]);
count += dp[m][n][k];
}
return count;
}评价总结
* 对特定问题（方案数量而不是具体方案）是简单了，但实际上压缩损失了很多信息 * 对方案数量的计算涉及到是否去重（可以通过 具体分配的是否递增来表达） * 对于有需求变化的场景会加大开发难度
方案2
思路代码
* 这是递归方案，遍历所有树枝 * 输出所有方案具体划分内容 * 时间复杂度 n^m 空间复杂度 m+结果数量
private static List<List<Integer>> partition(int n, int m) {
List<List<Integer>> result = new ArrayList<>();
partitionHelper(n, m, 0, new ArrayList<>(), result);
return result;
}
private static void partitionHelper(int n, int m, int last, List<Integer> current, List<List<Integer>> result) {
if (current.size() == m) {
if (n == 0) {
result.add(new ArrayList<>(current));
}
return;
}
int start = current.isEmpty() ? 1 : Math.max(current.get(current.size() - 1), 1);
int end = current.isEmpty() ? n/m : Math.min(n, last + 3);
for (int i = start; i <= end; i++) {
current.add(i);
partitionHelper(n - i, m, i, current, result);
current.remove(current.size() - 1);
}
}
public static void test() {
List<List<Integer>> result = partition(4, 2);
System.out.println(result.size());
for (List<Integer> partition : result) {
System.out.println(partition);
}
}评价
不是最切合题意的高效方式，但是符合问题生长方向文章来源：https://www.toymoban.com/news/detail-840620.html
过程可控，最后打印所有的方案内容文章来源地址https://www.toymoban.com/news/detail-840620.html
到了这里，关于算法题——华为OD机试——整数划分排序/员工分月饼——动态规划——Java的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
