文章目錄

• • 1 將長度為n的繩子分為m段求各段乘積的最大值
  • • 1.1 題目描述
    • 1.2 動態(tài)規(guī)劃法解題
    • 1.3 貪心法求解

1 將長度為n的繩子分為m段求各段乘積的最大值

1.1 題目描述

給你一根長度為 n 的繩子，請把繩子剪成 m 段 (m 和 n 都是整數(shù)，n>1 并且 m>1)每斷繩子的
長度記為 k[0],k[1],…,k[m].請問 k[0] k[1]…*k[m]可能的最大乘積是多少？

1.2 動態(tài)規(guī)劃法解題

動態(tài)規(guī)劃法：
看題目就知道這玩意要用動態(tài)規(guī)劃實現(xiàn)，可是就是不知道狀態(tài)轉(zhuǎn)移方程如何推導出來，費了九牛二虎之力才把別人的講解看懂，這思維根本不在一個層面啊，看來還是太菜，路漫漫兮。

先來看下動態(tài)規(guī)劃求解問題的四個特征：
①求一個問題的最優(yōu)解；
②整體的問題的最優(yōu)解是依賴于各個子問題的最優(yōu)解；
③小問題之間還有相互重疊的更小的子問題；
④從上往下分析問題，從下往上求解問題；

如下開始對題目進行分析：
有一段長度為n的繩子，我們現(xiàn)在要剪第一刀，我可以選擇下第一刀的地方有1 ~ n-1這些地方；比如長度為10的繩子，我第一刀可以在1~9這些地方下刀，共9種方式。

第一刀下去后，繩子分成兩部分，假設在i處下刀，繩子兩部分就分別為：[0 ~ i]與[i ~ n]，長度分為表示為i與n-i；那么找出第一刀最合適的位置，其實就是找i在哪下刀，可以使得[0 ~ i]與[i~n]的乘積最大，函數(shù)表示為：f(n)=max(f(i)×f(n?i))。

那么如何判斷i處切最大呢？這個時候，我們就要知道，[0~i]這個長度的繩子，任意方式切，最大的乘積是多少；假如說，當我們要切一個長度為10的繩子：切成1和9與4和6，兩種方式，哪個乘積更大？

回答：不光要考慮第一刀后兩個繩子的大小，還要考慮到9、4、6這三種情況，因為第一刀切出的繩子長度是否可以再切第二刀，使它有更大的乘積，比如將9再切成 3×3×3，6切成 4×2，哪個更大？

這種情況下，我們可以發(fā)現(xiàn)，無論再怎么切，一定是越切越短，那么我們是否可以將小于給定長度的繩子的每一個長度的最大乘積都求出來？

即：長度為10的繩子，我們就計算出：長度1~9這9種長度的繩子，每種長度的最大乘積是多少。 要求長度9的繩子的最大乘積，我們要知道1 ~ 8各個長度的最大乘積，要知道長度8的最大乘積，就要知道1 ~ 7長度的各個最大乘積，以此類推。

代碼分析如下：
f(n)定義為將長度為n的繩子分成若干段后的各段長度的最大乘積（最優(yōu)解），在剪第一刀時有n-1種剪法，可選擇在0 < i < n處下刀。在i處下刀，分成長度為i的左半繩子和長度為n-i的右半繩子，對于這兩根繩子，定義最優(yōu)解為f(i)和f(n-i)，于是f(n) = max(f(i) * f(n-i))，即求出各種相乘可能中的最大值就是f(n)的最優(yōu)解。就這樣從上到下的分下去，但是問題的解決從下到上。即先求出f(2)、f(3)的最優(yōu)解，然后根據(jù)這兩個值求出f(4)、f(5)…直到f(n)。
f(2) = 1，因為只能分成兩半；f(3) = 2，因為分成兩段21 大于分成三段的11*1。
…

public static int maxProductAfterCutting(int length){//長度小于2 無法分割if(length<2)return 0;//長度等于2 一分為二 1*1if(length==2)return 1;//長度等于3 最大為1*2=2if(length==3)return 2;//定義一個存放>=4 長度的數(shù)組 ，對>=4長度的最大的乘積進行臨時存儲int[] products=new int[length+1];//以下的前三個數(shù)組存放的不是最大值，而是長度值products[1]=1;products[2]=2;products[3]=3;for(int i=4;i<=length;i++) {int maxModify=0;for(int j=1;j<=i/2;j++) {int product=products[j]*products[i-j];if(product>maxModify)maxModify=product;} //得到f(i)的最優(yōu)解products[i]=maxModify;} //返回發(fā)f(n)return products[length];}

也可使用遞歸的方式進行求解：

int MaxProductCutting(int length) {if (length < 4){return length;}int max = 0;for (int i = 1; i <= length / 2; i++){int val = MaxProductCutting(i) * MaxProductCutting(length - i);if (val > max){max = val;}}return max; }int MaxProductAfterCutting1(int length) {if (length <= 1) return 0;if (length == 2) return 1;if (length == 3) return 2;return MaxProductCutting(length); }

1.3 貪心法求解

貪婪法，不斷分出長度為3的繩子，如果最后只剩下長度為1的繩子，退一步，將得到長度為4的繩子，然后將這長度為4的繩子分成22(這樣分是因為22大于原來的31)。因此n = 4時不能分出長度為3的繩子,而n = 2，n = 3可直接返回。當n >=5時候，滿足n >=5這個不等式的有2(n-2) > n以及3*(n-3) > n 。注意到2+n-2 = 3+n-3 = n,也就是說分出的兩個相乘的數(shù)要滿足和為n，且同樣的n，3*(n-3)的值更大，這就是為什么要不斷分出長度為3的繩子的原因。

代碼如下：

public static int maxProductAfterCutting2(int length) {// 長度為1時不滿足題意，返回0if (length < 2) {return 0;}// f(2)if (length == 2) {return 1;}// f(3)if (length == 3) {return 2;} // 統(tǒng)計能分出多少段長度為3的繩子int timesOf3 = length / 3;// 如果最有只剩下長度為1的繩子，需要退一步，得到長度為4的繩子，重新分成2*2的if (length - timesOf3 * 3 == 1) {timesOf3--;}// 到這步length - timesOf3 * 3的值只可能是0,2,4，所以timesOf2只可能是0, 1, 2int timesOf2 = (length - timesOf3 * 3) / 2;return (int) Math.pow(3, timesOf3) * (int) Math.pow(2, timesOf2); }

---

參考資料：

https://blog.csdn.net/u012429555/article/details/83184146

總結(jié)

以上是生活随笔為你收集整理的将长度为n的绳子分为m段求各段乘积的最大值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。