C++最大切分乘積問(wèn)題

圖 15-13   最大切分乘積的問(wèn)題定義

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

本題目標(biāo)是求得所有整數(shù)因子的最大乘積，即

我們需要思考的是：切分?jǐn)?shù)量 $m$ 應(yīng)該多大，每個(gè) $n_i$ 應(yīng)該是多少？

1.   貪心策略確定

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

如圖 15-14 所示，當(dāng) $n\ge 4$ 時(shí)，切分出一個(gè) $2$ 后乘積會(huì)變大，這說(shuō)明大于等于 $4$ 的整數(shù)都應(yīng)該被切分。

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

圖 15-14   切分導(dǎo)致乘積變大

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

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

貪心策略二：在切分方案中，最多只應(yīng)存在兩個(gè) $2$ 。因?yàn)槿齻€(gè) $2$ 總是可以被替換為兩個(gè) $3$ ，從而獲得更大乘積。

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

總結(jié)以上，可推出以下貪心策略。

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

2.   代碼實(shí)現(xiàn)

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

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

max_product_cutting.cpp

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

圖 15-16   最大切分乘積的計(jì)算方法

時(shí)間復(fù)雜度取決于編程語(yǔ)言的冪運(yùn)算的實(shí)現(xiàn)方法。以 Python 為例，常用的冪計(jì)算函數(shù)有三種。

• 運(yùn)算符 ** 和函數(shù) pow() 的時(shí)間復(fù)雜度均為 $O(\log ??a)$ 。
• 函數(shù) math.pow() 內(nèi)部調(diào)用 C 語(yǔ)言庫(kù)的 pow() 函數(shù)，其執(zhí)行浮點(diǎn)取冪，時(shí)間復(fù)雜度為 $O(1)$ 。

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

3.   正確性證明

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

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