C++最大切分乘積問題

圖 15-13   最大切分乘積的問題定義

假設我們將 $n$ 切分為 $m$ 個整數因子，其中第 $i$ 個因子記為 $n_i$ ，即

本題目標是求得所有整數因子的最大乘積，即

我們需要思考的是：切分數量 $m$ 應該多大，每個 $n_i$ 應該是多少？

1.   貪心策略確定

根據經驗，兩個整數的乘積往往比它們的加和更大。假設從 $n$ 中分出一個因子 $2$ ，則它們的乘積為 $2(n?2)$ 。我們將該乘積與 $n$ 作比較：

如圖 15-14 所示，當 $n\ge 4$ 時，切分出一個 $2$ 后乘積會變大，這說明大于等于 $4$ 的整數都應該被切分。

貪心策略一：如果切分方案中包含 $\ge 4$ 的因子，那么它就應該被繼續(xù)切分。最終的切分方案只應出現 $1$、$2$、$3$ 這三種因子。

圖 15-14   切分導致乘積變大

接下來思考哪個因子是最優(yōu)的。在 $1$、$2$、$3$ 這三個因子中，顯然 $1$ 是最差的，因為 $1\times (n?1)<n$ 恒成立，即切分出 $1$ 反而會導致乘積減小。

如圖 15-15 所示，當 $n=6$ 時，有 $3\times 3>2\times 2\times 2$ 。這意味著切分出 $3$ 比切分出 $2$ 更優(yōu)。

貪心策略二：在切分方案中，最多只應存在兩個 $2$ 。因為三個 $2$ 總是可以被替換為兩個 $3$ ，從而獲得更大乘積。

圖 15-15   最優(yōu)切分因子

總結以上，可推出以下貪心策略。

1. 輸入整數 $n$ ，從其不斷地切分出因子 $3$ ，直至余數為 $0$、$1$、$2$ 。
2. 當余數為 $0$ 時，代表 $n$ 是 $3$ 的倍數，因此不做任何處理。
3. 當余數為 $2$ 時，不繼續(xù)劃分，保留之。
4. 當余數為 $1$ 時，由于 $2\times 2>1\times 3$ ，因此應將最后一個 $3$ 替換為 $2$ 。

2.   代碼實現

如圖 15-16 所示，我們無須通過循環(huán)來切分整數，而可以利用向下整除運算得到 $3$ 的個數 $a$ ，用取模運算得到余數 $b$ ，此時有：

請注意，對于 $n\le 3$ 的邊界情況，必須拆分出一個 $1$ ，乘積為 $1\times (n?1)$ 。

max_product_cutting.cpp

/* 最大切分乘積：貪心 */
int maxProductCutting(int n) {
    // 當 n <= 3 時，必須切分出一個 1
    if (n <= 3) {
        return 1 * (n - 1);
    }
    // 貪心地切分出 3 ，a 為 3 的個數，b 為余數
    int a = n / 3;
    int b = n % 3;
    if (b == 1) {
        // 當余數為 1 時，將一對 1 * 3 轉化為 2 * 2
        return (int)pow(3, a - 1) * 2 * 2;
    }
    if (b == 2) {
        // 當余數為 2 時，不做處理
        return (int)pow(3, a) * 2;
    }
    // 當余數為 0 時，不做處理
    return (int)pow(3, a);
}

圖 15-16   最大切分乘積的計算方法

時間復雜度取決于編程語言的冪運算的實現方法。以 Python 為例，常用的冪計算函數有三種。

• 運算符 ** 和函數 pow() 的時間復雜度均為 $O(\log ??a)$ 。
• 函數 math.pow() 內部調用 C 語言庫的 pow() 函數，其執(zhí)行浮點取冪，時間復雜度為 $O(1)$ 。

變量 $a$ 和 $b$ 使用常數大小的額外空間，因此空間復雜度為 $O(1)$ 。

3.   正確性證明

使用反證法，只分析 $n\ge 3$ 的情況。

1. 所有因子 $\le 3$ ：假設最優(yōu)切分方案中存在 $\ge 4$ 的因子 $x$ ，那么一定可以將其繼續(xù)劃分為 $2(x?2)$ ，從而獲得更大的乘積。這與假設矛盾。
2. 切分方案不包含 $1$ ：假設最優(yōu)切分方案中存在一個因子 $1$ ，那么它一定可以合并入另外一個因子中，以獲取更大乘積。這與假設矛盾。
3. 切分方案最多包含兩個 $2$ ：假設最優(yōu)切分方案中包含三個 $2$ ，那么一定可以替換為兩個 $3$ ，乘積更大。這與假設矛盾。