总序

动态规划一般从两个角度来考虑：①状态表示，②状态计算
①状态表示
：即当前的状态可以用几维表示出来,包括：Ⅰ、集合，Ⅱ、属性
②状态计算
：如何能一步一步的将我们的状态计算出来。
如何能将我们当前的集合，化分成若干更小的子集，使得每一个都能算出来，都能用前面更小的子集表示出来（递归）

以上就是大名鼎鼎的闫氏dp法。Orz

时间复杂度：状态数量乘以转移数量

背包问题通常分为四大类：

        ①01背包、②完全背包、③多重背包、④分组背包

01背包问题是最基础的背包问题，以后所见到的背包问题都是从01背包衍生出来的。

大致区别：
01背包：给我们N个物体，以及容量是V的背包。物体的两个属性：体积vi, 价值wi（权重）。
        每件物品仅能使用一次（01背包的特征）
完全背包：给我们N个物体，以及容量是V的背包。物体的两个属性：体积vi, 价值wi（权重）。
        每件物体能使用无限次
完全背包：给我们N个物体，以及容量是V的背包。物体的两个属性：体积vi, 价值wi（权重）。
        每件物体能使用有限次
分组背包：给我们N组物体，以及容量是V的背包。物体的两个属性：体积vi, 价值wi（权重）。
         物品被划分为若干组，每组只能选一个。

 ①01背包

1、01背包一般用二维数组来表示状态
引入一个二维数组dp[ i ][ j ],来表示当前状态。其中i，j都是dp数组的属性。属性一般包括：体积、个数。而数组dp表示当前集合的某种状态(最大价值、最小价值、数量....)。在选择物体i时，只要满足选出来的总体积小于当前容积j，那么当前状态就是合法的，（在这里假设是要求的最大价值），最后在所有合法的状态里取一个最大价值（属性）即可
即：集合:所有只从前i个物品中选，并且总体积不超过j的选法
属性：集合中的最大值
2、状态计算。
我们在计算当前状态的价值时。分为两种情况
一、第一类选法，不包括i（此时的v[i] > j），即从[1,i)选择物品加入当前状态的背包中，且所选择的所有物品的总体积小于当前状态背包的容积。那么当前状态背包的总价值就等于前一个状态背包的总价值：dp[ i ][ j ] = dp[ i - 1 ][ j ];

二、第二类选法，包括i（此时的v[i] <= j），即从[1,i]中选择物品加入当前状态的背包中,且选择的所有物品的总体积小于当前状态背包的体积。
而第二类选法又可以分为：放入①物品i or ②不放入物品i(因为放入物品i，总价值会增加或者减少)
            比如：此时j = 5，f[i - 1][j]=5,而物品i的v[i] = 5,w[i] = 1;并且背包已经放满了，那么这种情况下放入物品i的前提就是舍弃前面的所有物品，并且造成总价值减少；如果j = 5，f[i - 1][j]=5,而物品i的v[i] = 1,w[i] = 10;并且背包剩余空间为1，那么放入物品i会使总价值增加。
①放入物品i
        既然放入物品i，那么就会造成背包的总空间减去v[i]而总价值加上w[i]: dp[ i ][ j ] = dp[ i -1 ][ j - v[i] ] + w[ i ];
②不放入物品i
        如果不放入物品i，那么此时背包的总价值等于上一种状态的总价值: dp[ i ][ j ] = dp[ i - 1 ][ j ]

 最后在在二者选择中取一个最大值即可：dp[ i ][ j ] = max(dp[ i - 1 ][ j ], dp[ i -1 ][ j - v[i] ] + w[ i ])

 题目：2. 01背包问题 - AcWing题库

代码： 

#include<bits/stdc++.h>

using namespace std;

int n,m;
//v表示当前物品i的体积，w表示当前物品i的价值
int v[1010],w[1010];
//f表示当时状态的总价值
int f[1010][1010];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    /*
        f[i][j] 表示一种状态，即选择前i个物品，最大体积不超过容积j时的最大价值。
        那么当状态为f[n][m]时，即表示选择前n个物品，体积不超过容积m时的最大价值
    */
    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ )
        {
            //如果新加入的物品i的体积v[i]大于容积j，那么就不能放入此此背包。此种状态的价值仍等于上一种状态的价值
            if(j < v[i])
                f[i][j] = f[i - 1][j];
            
            //在装与不装结果之中取一个最大值
            else 
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] +w[i]);
        }
        
    cout << f[n][m] << endl;
}

二维状态固然好，在O(m*n)的时间复杂度下求出每一种dp的状态
不过对于类似的背包问题，一般是求得最值，那么那么只需要求出最后一种dp的状态即可
固然会造成空间的浪费，比如每次求当前状态的f[i][j]，都是与前一种状态f[i - 1][j]有关，而与i - 2、i - 3都无关
所以我们可以通过两个变量，now、old不断滚动，让now永远指向当前最新的状态，old永远指向上一个状态，进行交替滚动，那么问题就迎刃而解了
不过这种做法虽然极大的节省了空间，不过也将除了最后一种与前一种dp状态保留外，其余的状态全部丢失了

优化：

代码：

#include<bits/stdc++.h>

using namespace std;

int n,m;
int v[1010],w[1010];
//f表示价值
int f[1010][1010];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    int now = 1, old = 0;
    for(int i = 1; i <= n; i ++ )
    {
        //让now永远指向当前状态
        swap(now,old);
        for(int j = 0; j <= m; j ++ )
        {
            f[now][j] = f[old][j];
            if(j >= v[i]) f[now][j] = max(f[now][j], f[old][j - v[i]] +w[i]);
        }
        
    }
        
    cout << f[now][m] << endl;
}

当然，也可以自我滚动
这里的遍历是从大到小 ，每次f[i][j]在更新的时候都是依托于f[i - 1][...]来进行更新（f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);），那么如果降维后j仍从小到大遍历的话，由于上一个价值会被新的价值所覆盖（先计算j - v[i]在赋值给j）；如果j从大到小遍历的话则无

代码：

#include<bits/stdc++.h>

using namespace std;

int n,m;
int v[1010],w[1010];
//f表示价值
int f[1010];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i ++ )
        for(int j = m; j >= v[i]; j -- )//注意，要从大到小
            f[j] = max(f[j], f[j - v[i]] +w[i]);
        
        
    cout << f[m] << endl;
}

②完全背包

解决完全背包即是将完全背包问题转化为01背包进行求解。假设我们对于第i个物品，取或不取第k*i个物品来进行。
那么类似于01背包的分析。两类选法的总价值分别是：
第一类:不能选则第i个物品的k倍：dp[ i ][ j ] = dp[ i - 1 ][ j ]
第二类:能选择第i个物品的k倍
取第i个物品的k倍：dp[ i ][ j ] = max(dp[ i ][ j ], dp[ i -1 ][ j -  k*v[i] ] + k * w[i];
不取第i个物品的k倍：dp[ i ][ j ] = dp[ i - 1 ][ j ] 
而当k == 0时，dp[ i ][ j ] = max(dp[ i ][ j ], dp[ i - 1][ j ])
所以总价值即为：dp[ i ][ j ] = max(dp[ i ][ j ], dp[ i -1 ][ j -  k*v[i] ] + k * w[i];

题目：AcWing 3. 完全背包问题 - AcWing

代码：

#include<iostream>
#include<algorithm>

using namespace std;

int n, m;
int dp[1010][1010], v[1010], w[1010];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ )
            for(int k = 0; k * v[i] <= j; k++)
                dp[i][j] = max(dp[i][j],dp[i - 1][j - k * v[i]] + w[i] * k);


    cout << dp[n][m];

    return 0;
}

优化①

——降成二维：
f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i],f[i - 2][j - 2*v[i]] + 2 * w[i],...)
f[i,j - v] = max(         f[i - 1][j - v[i]],         f[i - 2][[j - 2*v[i]] + w[i],...）
注意：由于0 <= k <= ∞，那么只要体积够就会一直选下去，不存在最后一项
我们可得知：f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i])
代码：

#include<iostream>
#include<algorithm>

using namespace std;

int n, m;
int dp[1010][1010], v[1010], w[1010];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

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



    cout << dp[n][m];

    return 0;
}

 上述核心代码也可以写为：

/*
因为第一种不包含k 倍的物品i  与第二种的包含了k 倍的物品i，但是不取k 倍的物品i所更新的价值是一样的，所以可以合并到一块
*/
#include<iostream>
#include<algorithm>

using namespace std;

int n, m;
int dp[1010][1010], v[1010], w[1010];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

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



    cout << dp[n][m];

    return 0;
}

将数组优化到一维：

#include<iostream>
#include<algorithm>

using namespace std;

int n, m;
int dp[1010], v[1010], w[1010];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i ++ )
        for(int j = v[i]; j <= m; j ++ )
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

    cout << dp[m];

    return 0;
}

这里完全背包不像01背包那样需要从大到小遍历的原因是：
01背包更新时：dp[i][j] = max(dp[ i ][ j ], dp[ i - 1][ j - v[i] ] + w[i])
完全背包更新时：dp[ i ][ j ] = max(dp[ i ][ j ], dp[ i ][ j - v[i] + w[i])
01背包每次更新时借助前一个状态，如果从小到大遍历，那么就会造成覆盖；完全背包则是借助当前状态进行更新，不会存在覆盖问题。

Q:为什么可以优化到一维
A:dp的优化，即是对朴素做法的优化，即优化之后的代码与朴素代码等价：
 

/*
因为第一种不包含k 倍的物品i  与第二种的包含了k 倍的物品i，但是不取k 倍的物品i所更新的价值是一样的，所以可以合并到一块
*/
#include<iostream>
#include<algorithm>

using namespace std;

int n, m;
int dp[1010][1010], v[1010], w[1010];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ )
            {
                dp[i][j] = dp[i -1][j];
                /*
                    优化之前的当前的价值等于上一层价值
                    而优化后:dp[j] = dp[j]。由于赋值顺序从右向左
                    而右边的价值为上一层的价值(未被更新)，
                    所以赋值给当前价值时，是上一层的价值。故等价
                */
                if(j >= v[i]) dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]);
                /*
                    上一层与更新了的当前层价值取一个最大值
                    优化后dp[j] = max(dp[j], dp[j - v[i]] + w[i])
                    dp[j]没有被更新，所以仍为上一层。    
                    而dp[j - v[i]]被更新了，所以为当前层。故等价
                */
            }
    cout << dp[n][m];

    return 0;
}

多重背包

对于多重背包而言仍转化为01背包进行求解。
这里采用二进制的优化方式
假设物品我们有1023个，普通枚举的话需要从第0个枚举到第1023个物品
分组：1，2，4，8，...，512
若先取第一组，则可以枚举0~1个物品，若加上第二组则可以枚举0~3个物品...加上最后一组，则可以枚举0~1024个物品
那么问题就迎刃而解了，将1023分成10组，第一组到第10组分别为：1，2，4，8，...，512
所以只要询问当前的一组是否取还是不取就行了，那么取与不取的问题即是01背包的问题。大大降低时间复杂度，从N*V*S 变为 N*V*logS。

但是通常来说物品的个数没有那么巧，比如物品个数为1000
那么分组的时候仍分成10组，即1，2，4，8，...，256，489。第十组不再是512，因为第十组若是512的话，那么表示的物品即为0~1023而不是1000，所以第十组的个数等于物品的总个数-前九组的个数即可，所以第十一组的个数为1000-511=489个。
这就是二进制的绝妙运用

将所有种类的物品，分成不同组后，剩下的就是对该组进行取与不取的操作即：01背包

举一个买苹果的例子：假设你要去采购1023个苹果，且苹果的各项指标均相同，选与不选纯看你自己的心情。那么你可以在市场上对每一个苹果进行选与不选的操作，那么操作需要进行1023次。但是如果此时商家已经将1023个苹果分为十组，分别为：1，2，4，8，...，512个苹果，那么接下来你只需要对每一组苹果进行选与不选的操作即可，操作仅需要进行10次。(不太严谨）

题目：4. 多重背包问题 I - AcWing题库

 分析本题的状态表示与状态计算
一、状态表示：dp[i][j]
①集合：有 N种物品和一个容量是 V的背包，第i种物品最多有s件，求体积不超过j的所有方案的集合
②属性：总价值的最大值
二、状态的计算
如何将集合划分出来。
我们可以对第 i 种物品的s件，划分成0、1、2、... 、s的集合。即对该集合的每一个子集取与不取进行划分。那么即可转化为朴素版的完全背包：dp[ i ][ j ] = max(dp[ i ][ j ], dp[ i - 1][ j - k * v[ i ] ] + k * w[ i ])。
而本题三重循环N*V*S=1e6,时间复杂度不高，朴素版的可以过掉

代码：

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 105;
int n, m;
int v[N], w[N], s[N];
int dp[N][N];

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i];
    
    //完全背包的朴素版
    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ )
            for(int k = 0; k <= s[i] && k * v[i] <= j; k ++ )
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
                
    cout << dp[n][m] << endl;
    
    return 0;
}

 如果复杂度很大，那么就要考虑像完全背包那样优化了。
完全背包的优化方式：f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i],f[i - 2][j - 2*v[i]] + 2 * w[i],...)
                                    f[i,j - v] = max(         f[i - 1][j - v[i]],         f[i - 2][[j - 2*v[i]] + w[i],...）
多重背包优化：dp[i][j] = max(dp[i-1][j], dp[i-1][j-v]+w, ..., dp[i-1][j-s*v]+s*w)
                         dp[i][j-v]=max(            dp[i-1][j-v],...,    dp[i-1][j-s*v]+(s-1)*w, dp[i-1][j-(s+1)*v]+s*w)
我们可以发现多重背包多出来一项，所以不能像完全背包那样对多重背包进行优化
原因：多重背包可以选无数次即选择的区间为[0,∞），只要体积够就可以一直选，且当趋近于∞时，即是项数多一项也不会影响。
            完全背包可以选有限次即选择的区间为[0, s)，即是体积够也不可以一直选，且当选择次数为s时，数值的大小是严格区分的。
所以只能采用二进制的方式进行求解

二进制优化：

题目：5. 多重背包问题 II - AcWing题库

 朴素版的三重循环，时间复杂度为：2e9，复杂度太高。直接写会tle

二进制优化：

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

//总共N种物品，每种物品S个，那么最多即可分为N*log S组
const int N = 12010, M=2010;
int n, m;
int v[N], w[N];
int dp[M];

int main()
{
    cin >> n >> m;
    //一开始的组别为0
    int cnt = 0;
    for(int i = 1; i <= n; i ++ ) 
    {
        int a,b,s;
        cin >> a >> b >> s;
        
        int k = 1;//转化为二进制的媒介
        while(s >= k)
        {
            //开始对当前这一种物品进行分组
            cnt ++;
            v[cnt] = k * a;//当前组的体积等于当前组的个数乘以每个物品的体积
            w[cnt] = k * b;//同理
            s = s-k;//让总个数减去当前已经被分完组的个数
            k *= 2;//二进制
        }
        
        if(s > 0)//如果还有剩余值，那么改值一定不足以满足上述下一次二进制的分组
        {
            //那么就对剩下的s个物品进行单独分组
            cnt ++;
            v[cnt] = s * a;
            w[cnt] = s * b;
        }
    }
    
    //对cnt组进行选与不选——01背包
    for(int i = 1; i <= cnt; i ++ )//组
        for(int j = m; j >= v[i]; j -- )//体积
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
            
    cout << dp[m] << endl;
    
    return 0;
}

分组背包：

①状态表示。一、集合：只从前i组物品中选，且总体积不大于j的所有选法；二、属性：求所有选法当中的最大价值
②状态计算。将集合划分出来，可以对比着完全背包来进行划分
完全背包问题：选择第i组里的多少个
分组背包问题：选择第i组里的某一个

题目：9. 分组背包问题 - AcWing题库

 代码：

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 105;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

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];//第i组，j个物品的体积与价值
    }
    
    for(int i = 1; i <= n; i ++ )
        for(int j = m; j >= 0; j -- )//转化为完全背包问题，优化成一维时，体积需要从大到小遍历
            for(int k = 1; k <= s[i]; k ++ )//第i组最多有s[i]个物品
                if(v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    
    
    cout << f[m] << endl;
    return 0;
}