最近寫了很多dp的題目，狀態方程只要轉換出來，就特別簡單，所以特意去研究了一下，怎么去做dp的題目，一下是一些見解，

背包問題

背包問題是dp問題的常客了，一般來說只要能將狀態方程轉換出來，就很好寫，那么怎么樣才能很快速的寫出狀態方程呢？emmm貌似沒有什么好辦法哈哈，多寫就好了，只要把dp的題目型別都見一遍，那么狀態方程就不是什么難事了，

01背包

有 N 件物品和一個容量是 V 的背包，每件物品只能使用一次，

第 i 件物品的體積是 vi，價值是 wi，

求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大，
輸出最大價值，

上面這個就是很經典的01背包，那么首先狀態方程是啥，狀態方程其實就是我們怎么看他，怎么去分析他的程序，這個二維的狀態方程事f[i][j]，意思是從前i個物品中選，體積不超過j的價值，根據題目意思，故該方程的屬性事max,所以是從前i個物品中選，體積不超過j的最大價值，

 for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            if(j>=v[i])
            f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }

完全背包

有 NN 種物品和一個容量是 VV 的背包，每種物品都有無限件可用，

第 ii 種物品的體積是 vivi，價值是 wiwi，

求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大，
輸出最大價值，

   for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            if(j>=v[i])f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
        }

我們可以發現完全背包問題和01背包問題代碼只相差一點點一個是max：f[i-1][j-v[i]]+w[i]，一個是max：f[i][j-v[i]]+w[i]，為什么呢，這里面其實有個轉換，

這個圖是從acwing上找的：完全背包（順便y總yyds），通過這個轉換，我們就很清晰的知道了為什么是f[i][j-v[i]]+w[i]，然后根據我們的狀態表示從前i個物品中選，體積不超過j的最大價值，故最后答案就是f[n][m](假設n個物體，最大體積是m)

多重背包

多重背包的題目如果資料較小是可以直接o（n^3）暴力去求解的，狀態表示還依舊是從前i個物品中選，體積不超過j的最大價值，所以狀態方程就是f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

   for(int i=1;i<=n;i++)//列舉所有物品
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            for(int k=0;k<=s[i]&&k*v[i]<=j;k++)//列舉拿一個，拿兩個....的情況
            {
                
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
            }
        }

但是這個是暴力的解法，假如資料很大呢？比如資料到了1000？，那么10^9肯定會超時，這時候我們可能回想能不能優化成01背包?把每一個三份物體全部看作是三個一份的物體，然后用01背包的思路去做是不是更好？但是一個一個的分實在是太慢了，除了一份一份的分從達到表達原來物體份數的方法，還有沒有別的更好的呢？這個時候就要用到背包問題的二進制優化方法:

比如隨便一個數字：15，我們可不可以用最少的數字去表示，答案是可以找到的，我們可以用1，2，4，8去表示從0~15所有的數:0一個都不選，1選1，2選2，3選1+2，4選4，5選......14選2+4+8，15選1+2+4+8，如果折射到一般情況的話就是：

        
int n;//定義任意一個自然數
vector<int> f
cin>>n;
int N=n;
for(int j=1;j<=n;j*=2)
{
    n-=j;
    f.push_back(j)       
}

if(n>0)f.push_back(n);//假如s大于0說明，說明現在陣列的數可以組成N-n的整數，所以要加上剩下的n
     

這樣我們就把拆分成份的時間復雜度優化成了o（logn），

我們已經通過二進制把物體都拆成了只能選一次的各個子物體，這樣子就可以直接用01背包去做就可以了

/*
有 N 種物品和一個容量是 V 的背包，

第 i 種物品最多有 si 件，每件體積是 vi，價值是 wi，

求解將哪些物品裝入背包，可使物品體積總和不超過背包容量，且價值總和最大，
輸出最大價值，

輸入格式
第一行兩個整數，N，V，用空格隔開，分別表示物品種數和背包容積，

接下來有 N 行，每行三個整數 vi,wi,si，用空格隔開，分別表示第 i 種物品的體積、價值和數量，

輸出格式
輸出一個整數，表示最大價值，
*/
const int N = 2010;
vector<pair<int,int >> vw;
int n,m;
int v,w,s;
int f[N];
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>v>>w>>s;
        for(int j=1;j<=s;j*=2)
        {
            s-=j;
            vw.push_back({j*v,j*w});
        }
        if(s>0)vw.push_back({s*v,s*w});
    }
   
    for(int i=1;i<=vw.size();i++)
    {
        for(int j=m;j>=0;j--)
        {
            auto t=vw[i-1];
            f[j]=f[j];
            if(j>=t.first)f[j]=max(f[j],f[j-t.first]+t.second);
        }
    }
        cout<<f[m];
    return 0;
}

分組背包

有 N 組物品和一個容量是 V 的背包，

每組物品有若干個，同一組內的物品最多只能選一個，
每件物品的體積是 vij，價值是 wij，其中 i 是組號，j 是組內編號，

求解將哪些物品裝入背包，可使物品總體積不超過背包容量，且總價值最大，

輸出最大價值

經過以上的各種背包問題的洗禮，這個就比較容易想到這個的狀態表示方程（才不是因為每個背包問題的狀態表示都一樣...）從前i組（注意這里是不同的這里是“組”）物品中選，體積不超過j的最大價值，

剩下的就和之前01背包一樣了：

/*
有 N 組物品和一個容量是 V 的背包，

每組物品有若干個，同一組內的物品最多只能選一個，
每件物品的體積是 vij，價值是 wij，其中 i 是組號，j 是組內編號，

求解將哪些物品裝入背包，可使物品總體積不超過背包容量，且總價值最大，

輸出最大價值，

輸入格式
第一行有兩個整數 N，V，用空格隔開，分別表示物品組數和背包容量，

接下來有 N 組資料：

每組資料第一行有一個整數 Si，表示第 i 個物品組的物品數量；
每組資料接下來有 Si 行，每行有兩個整數 vij,wij，用空格隔開，分別表示第 i 個物品組的第 j 個物品的體積和價值；
輸出格式
輸出一個整數，表示最大價值，
*/
const int N = 110;
int f[N];
int v[N][N],w[N][N],s[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        for(int j=1;j<=s[i];j++)
        {
            cin>>v[i][j]>>w[i][j];
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
            for(int k=1;k<=s[i];k++)
            {
                if(j>=v[i][k])f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
            }
    
    cout<<f[m];
    return 0;
}

背包類dp結束

（以上就是本菜雞學習下來的一點點心得體會吧，希望能幫到大家---y總的思路是真的好www）

學習網站acwing