乙個關於演算法的問題。 應使用動態規劃。 正確答案是乙個加分項。

這個問題來自**啊，很有意思。

我想到了乙個想法，但我沒有使用動態規劃，而是稱之為“可行逐次逼近法”，想法如下：

1.資料結構。

a[n]、pailie_a[n]、

2.想法。 1）得到初始次優可行解n

將a[n]從小到大排列，排列後仍儲存在a[n]中，a[1]儲存最小值，a[n]儲存最大值;

重排後，每個元素的初始位置數儲存在pailie a[n]中，如果重排後最小值儲存在a[1]中，原始狀態儲存在a[k]中，則pailie a[1]=k;

確定是否有可行的解決方案：

取 a[n] 的前 x 個最小值並儲存在 solve[x] 中以計算 sum（solve[x]），如果超過給定值，則沒有可行的解;

否則，有乙個可行解，此時的求解[x]是初始次優可行解，a[n]中的其餘元素儲存在qita[n-x]中備用;

2）最優解的逐次逼近：

順序：將 solve[x] 中的元素替換為 qita[n-x] 中的元素;

直到：滿足停止標準：將 solve[x] 中的任何元素替換為 qita[n-x] 中的任何元素不會產生更好的結果。

未完待續.........

01 背包問題，具體《背包九言》，由ACM之神撰寫。

對動態規劃演算法的基本基礎進行了修正，以求最優子結構和重疊子問題。

1.最佳的子結構。 當問題的最優解包括其子問題的最優解時，該問題被稱為具有最優子結構的性質。 該問題的最優子結構為該問題可以通過動態規劃演算法求解提供了重要線索。

2.在動態規劃演算法中，利用問題的最優子結構性質，從子問題的最優解中，以自下而上的方式逐步構建整個問題的最優解。

3.重疊的子問題。 可以用動態規劃演算法解決的問題的另乙個基本要素是子問題的重疊性質。 可以用動態規劃演算法解決的問題的另乙個基本要素是子問題的重疊性質。

當使用遞迴演算法自上而下地解決問題時，每次出現的子問題並不總是新的，並且一些子問題需要重複計算多次。

動態規劃演算法的優缺點：

1、與其他演算法相比，動態規劃大大減少了計算量，豐富了計算結果，不僅能找到從當前狀態到目標狀態的最優值，還能找到中間狀態的最優值，這對很多實際問題都非常有用。

2、與一般演算法相比，動態規劃也有一定的缺點：占用空間過多，但對於空間需求小的問題，動態規劃無疑是最好的方法！ 動態規劃演算法和貪婪演算法都是構造最優解的常用方法。

動態規劃演算法沒有上公升前方搜尋的固定解模式，非常熟練。

3.動態規劃演算法利用該子問題的重疊性，每個子問題只求解一次，然後將其解儲存在乙個**中，當再次需要該子問題時，只需用恆定時間檢查結果即可。

1.描述最優解的結構特徵。

2. 遞迴定義最優解的值。

3. 自下而上計算最優解的值。

4. 根據計算資訊構造最優解。

一、基本概念。

動態規劃過程是乙個過程，其中每個決策都取決於當前狀態，然後導致狀態偏移。 決策序列是在變化狀態下產生的，因此這種多階段最優決策和解決問題的過程稱為動態規劃。

2.基本思想和策略。

其基本思想類似於分治法，即把要解決的問題分解成若干個子問題（階段），按順序解決子階段，前乙個子問題的求解為後乙個子問題的求解提供了有用的資訊。 在解決任何子問題時，列出各種可能的區域性解決方案，並決定保留那些可能是最佳的解決方案，並丟棄其他解決方案。 子問題依次求解，最後乙個子問題是初始問題的求解。

由於動態規劃求解的大多數問題都具有子問題重疊的特點，為了減少重複計算，每個子問題只求解一次，並將不同階段的不同狀態儲存在乙個二維陣列中。

與分而治之法最大的區別在於，通過分解得到的子問題往往不是相互獨立的（即下乙個子階段的解是在前乙個子階段的解的基礎上，進一步求解的）。

三、適用情形。

動態規劃可以解決的問題通常具有三個屬性：

優化原則：如果問題的最優解包含同樣最優的子問題的解，則稱該問題具有最優子結構，即滿足優化原則。

無後遺症：即一旦確定了某個階段狀態，就不受該狀態未來決策的影響。 也就是說，乙個狀態之後的過程不影響以前的狀態，而只影響當前狀態。

3）存在重疊的子問題：即子問題之間不是相互獨立的，乙個子問題在下一階段的決策中可能會被多次使用。（此屬性對於應用動態規劃不是必需的，但如果沒有它，動態規劃演算法與其他演算法相比沒有優勢）。