動態規劃之背包問題

動態規劃（Dynamic Programming，簡稱DP）動態規劃常常適用於有重疊子問題和最優子結構性質的問題，動態規劃方法所耗時間往往遠少於樸素解法。

動態規劃背後的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再合並子問題的解以得出原問題的解。 通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，從而減少計算量： 一旦某個給定子問題的解已經算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表。 這種做法在重復子問題的數目關於輸入的規模呈指數增長時特別有用。雖然抽象後進行求解的思路並不復雜，但具體的形式千差萬別，找出問題的子結構以及通過子結構重新構造最優解的過程很難統一，為瞭解決動態規劃問題，隻能靠多練習、多思考瞭。

*動態規劃問題滿足三大重要性質*

最優子結構性質：如果問題的最優解所包含的子問題的解也是最優的，我們就稱該問題具有最優子結構性質（即滿足最優化原理）。最優子結構性質為動態規劃算法解決問題提供瞭重要線索。

子問題重疊性質：子問題重疊性質是指在用遞歸算法自頂向下對問題進行求解時，每次產生的子問題並不總是新問題，有些子問題會被重復計算多次。動態規劃算法正是利用瞭這種子問題的重疊性質，對每一個子問題隻計算一次，然後將其計算結果保存在一個表格中，當再次需要計算已經計算過的子問題時，隻是在表格中簡單地查看一下結果，從而獲得較高的效率。

無後效性：將各階段按照一定的次序排列好之後，對於某個給定的階段狀態，它以前各階段的狀態無法直接影響它未來的決策，而隻能通過當前的這個狀態。換句話說，每個狀態都是過去歷史的一個完整總結。這就是無後向性，又稱為無後效性。

重點 dp數組的含義 + 狀態轉移方程 （具體問題具體分析）

首先背包問題是我們接觸動態規劃必須接觸的的經典問題，重要的問題說三遍，經典經典經典。

• 0-1背包問題
• 完全背包問題
• 多重背包問題

0-1背包問題

1、題目描述

​這裡你有N件物品和一個容量為M的背包，這N件物品的第 i 件物品的 價值是V[i] ，重量是W[i].問題是拿取這N件物品的哪幾件時，使得背包可以裝下（意思就是物品的重量總和小於或等於M）且價值最大。

關鍵問題：其實這堆物品在你選擇的時候無非就是兩種路子可以選擇：選 or 不選

第一步：構建dp數組的含義，dp[i][j] ：代表的是前 i 個物品加入容量為 j 的背包裡面價值總和的最大值

第二步：分析狀態轉移方程

​ 對於一個物品來說：要麼選要麼不選，

• 選擇這個物品：就是第i件物品放入背包中，此時