背包問題概念：
背包問題是一種經典的組合優化的NP問題，在計算機科學、運籌學等領域有著廣泛的應用。
問題可以簡單的描述為：
假設有一個容量為C的背包和n個物品，每個物品i都有重量w[i]和價值v[i]。目標是選擇一些物品放入背包，使得放入背包的物品總價值最大，同時背包中物品的總重量不能超過背包的容量。
?
?這里先簡單介紹兩種背包問題：
1.01背包：也就是你物品的個數是1個，你拿了就剩0個，沒拿就剩1個
2.完全背包：物品個數無數個，可以拿0/1/2/3/4至無窮多個
背包也可以分兩種：1.背包不需要裝滿。2.背包必須裝滿
這樣兩兩組合就有4種問題
其實背包問題還有很多種情況，個數有2/3/4/5等等，每個在X2（不必裝滿||必須裝滿）
這里重在了解01背包和完全背包問題（其他可能更多出現在競賽中）
01背包問題是所有問題的基礎（基本上所有的背包問題都衍生于01背包）
以牛客網例題為例（leetcode沒有較好的入門例題）
題目解析：?
第1小問：背包不必裝滿問題
第2小問：背包必裝滿問題
建議畫一個表格，而且最好上面標號，就有點像我們之間處理初始化那里一樣，多加一行多加一列，有利于我們后面填表
算法原理 ：
其實這里的背包問題就是一個線性dp問題，也就是你挑物品時可以從左往右依次選還是不選
類似于我們之前講解線性dp問題一樣去分析即可
1.狀態表示：經驗+題目要求
經驗：以i位置為結尾巴拉巴拉
題目要求：dp[i]:表示以i位置為結尾（從前i個物品中）所有的選法中價值最大的
我們可以發現這個狀態表示推導不出來狀態轉移方程，因為我們在考慮第i個物品的時候，需要考慮這個能不能放進背包，我連總的重量和剩余容量都不知道
所以我們需要改一下狀態表示，既然一維表示不了，那我們就二維
dp[i][j]:從前i個物品挑選，總體積不超過j，所有選法中，能挑選出來的最大價值
為什么這里是不超過？因為我們做第一小問，問題是不需要裝滿
2.狀態轉移方程：以最近的一步狀況，劃分情況
1.不選i物品，不選的話是不是最大價值就在i-1前，回歸我們的狀態表示
dp[i-1][j]:從前i-1個物品挑選，總體積不超過j，所有選法中，能挑選出來的最大價值?
那這種選法中dp[i][j]=dp[i-1][j]
2.選i物品，選的時候是不是要考慮能不能裝進背包，所以我們需要判斷背包剩余容量
剩余容量就是j-v[i]
如果剩余容量小于0，那這個i物品肯定是不能選的
如果剩余容量大于等于0，這個i物品就可以選，怎么選，回歸狀態表示
是不是你自身的價值加上i-1的最大價值
所以綜上，最大價值就是這兩種選法中最大的那個
第2小問講解：
這里只需要稍加修改一下狀態表示即可
原： dp[i][j]:從前i個物品挑選，總體積不超過j，所有選法中，能挑選出來的最大價值
現：dp[i][j]:從前i個物品挑選，總體積正好等于j，所有選法中，能挑選出來的最大價值
基本是一樣的，但我們需要特別注意：我們用dp[i][j]=-1,表示沒有這種情況，就是所有的選法無法湊到剛好總體積等于j的情況
那為什么不等于0呢？因為如果等于0，我們就無法區分dp[i][j]=0時表示什么情況，我們之前做第一問的時候就有初始化為0，為了區分這兩種情況，我們把湊不出總體積為j的情況設為-1
第一種情況不選i物品，可以不用判斷dp[i-1][j]!=-1,因為我不選i物品，dp[i-1][j]都等于-1，那證明你湊不出來，那dp[i][j]也湊不出來，所以這時候的dp[i][j]=dp[i-1][j];
第二種情況，選i物品，就必須要判斷dp[i-1][j-v[i]]?:也就是你必須要判斷你前面的必須要湊出來j-v[i]的體積，因為你dp[i][j]這個位置選i物品要加體積v[i]的，所以你前面要能湊出來，這時候在加上v[i]的體積就剛剛好
初始化：明確第一行第一列表示啥，第一行我從0個物品中選還是不選湊出體積為0/1/2/3
第一列我選不選0/1/2/3/4物品，湊0體積，那就說明都不選，價值就是0，為了方便，我們只要創建dp表的時候初始化第一行為-1即可
后面的都和第一小問一模一樣了
?
優化 ：
第一種方法：滾動數組的方法，我們可以發現我們的狀態轉移方程僅僅需要兩行的數組
也就是我們在填這一行的數據時，僅僅需要上一行的數據
例如我們在填寫第一行數據時，僅僅需要第0行的數據，那我們填第2行時，就可以把第0行滾動下來充當第2行
?
如果你還覺得兩行數組很麻煩，當然也可以用一行數組，
但需要注意你的填表順序要從右往左
如果你是左往右，你填表的時候需要借助左上角的值，那左往右就是覆蓋，填右邊的時候就出錯
這里運用的原理就是覆蓋，你的數組原來是有數據的，也就是上一行的數據，你填這一行時就可以用到這個數據，注意填表從右往左就行（因為你只有一行數組）?
