簡介

一個考察動態(tài)規(guī)劃的機(jī)試題的數(shù)學(xué)模型建立，和兩種思路的取舍

題目

公司分月餅，m個員工，買了n個月餅，m <= n，每個員工至少分一個月餅，但是也可以分到多個，單人分到最多月餅的個數(shù)是Max1，單人分到第二多月餅個數(shù)是Max2。

但需要滿足Max1-Max2 <= 3，單人分到第n-1多月餅個數(shù)是Max(n-1)，單人分到第n多月餅個數(shù)是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，滿足要求）

平臺場景

?？途W(wǎng) 可以選擇使用多種語言 我選擇Java寫的

大多數(shù)題目需要做輸入輸出訓(xùn)練

但是這題不用 給定了 形參 m員工 n月餅 最后return方案數(shù)量即可

數(shù)學(xué)模型

把正整數(shù)n分為m份自然數(shù)，m <= n，排序后，任意相鄰數(shù)相差不超過3

方案1-動態(tài)規(guī)劃

思路代碼

* 這是動態(tài)規(guī)劃方案
* 定義狀態(tài) dp[i][j][k] 表示前 i 個人分配了 j 個月餅，且第 i 個人分配了 k 個月餅的方案數(shù)。
* 狀態(tài)方程為 dp[i][j]=∑k=1>>3? dp[i?1][j?k]
* 時空復(fù)雜度都是 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個員工時，只有一種分法
        }
        // 動態(tài)規(guī)劃
        for (int i = 1; i <= m; i++) {
            for (int j = i; j <= n; j++) { // 確保月餅數(shù)量不少于員工數(shù)
                for (int k = 1; k <= j; k++) { // 每個員工至少分得1個月餅
                    for (int l = 1; l <= k; l++) { // 確保當(dāng)前分配不超過上一個員工的分配
                        dp[i][j][k] += dp[i - 1][j - k][l];
                    }
                }
            }
        }

        // 匯總結(jié)果
        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;
    }

評價總結(jié)

* 對特定問題（方案數(shù)量而不是具體方案）是簡單了，但實(shí)際上壓縮損失了很多信息
* 對方案數(shù)量的計算涉及到是否去重（可以通過 具體分配的是否遞增來表達(dá)）
* 對于有需求變化的場景會加大開發(fā)難度

方案2

思路代碼

* 這是遞歸方案，遍歷所有樹枝
* 輸出所有方案具體劃分內(nèi)容
* 時間復(fù)雜度 n^m 空間復(fù)雜度 m+結(jié)果數(shù)量

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

評價

不是最切合題意的高效方式，但是符合問題生長方向

過程可控，最后打印所有的方案內(nèi)容文章來源地址http://www.zghlxwxcb.cn/news/detail-840620.html

到了這里，關(guān)于算法題——華為OD機(jī)試——整數(shù)劃分排序/員工分月餅——動態(tài)規(guī)劃——Java的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！