看了看评论，发现有好多朋友滚动数组没掌握，所以干脆从头讲到尾，如果觉得自己掌握某一部分的可以跳过

0-1背包之非滚动数组

题目
https://www.acwing.com/problem/content/submission/code_detail/2231935/
这里就把代码拿出来说一下，题目就是本网站的 01背包问题
首先思路
现在有a件物品，每件物品都有他自己的价值与体积，因为每件只能放一次，那么咱们就按先后顺序一个一个拿起来判断，看能不能装下，若是能装下，看要不要拿，要不要拿肯定是看此时拿了的话能否构成此时的最优解。要判断是否是该状态下的最优解肯定要判断如果将该物品放入刚好满的话，那放他之前的最优解是什么。转换一下思维就是要求以
背包容积-该物品容积
为容积的背包装之前的物品的最优解【并不包括本物品以及之后的物品】。那么咱们就要通过从1遍历背包的容积来判断最优解，这就是所谓的基于之前的数据。

现在总结下思路
咱们要做这道题就要挨个物品判断要不要拿能不能拿，同时通过遍历背包容积判断每个容积下的最优解，以此来判断该种物品究竟拿了能不能带到此时的最优解。用二维数组dp[i-1][x],就可以完美的表示第i件物品之前容积为x时的最优解（第i件物品和它后面的物品都不可能在这个背包）

下来用代码解释

#include <bits/stdc++.h>



using namespace std;
#define the_smallest_unit 0.5
#define item_max 1005
int dp[item_max][item_max];
int m, n;
int item_v[1005], item_w[1005];
int main(void)
{
//输入
    cin >> n >> m;
    int i, j, k;
    for(i=1;i<=n;i++)
    {
        cin >> item_w[i] >> item_v[i];
    }
    //正题
    //一维遍历物品看要不要拿，二维遍历背包容积，然后在数组中存储该状态下的最优价值，
    //那么在判断下一个物品时就能直接使用该最优解
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
        {
            if (j >= item_w[i])//能装下
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - item_w[i]] + item_v[i]);//看拿不拿，肯定选最优解
                //此时的dp[i - 1][j - item_w[i]]就是判断该物品之前容积为j-该物品容积的背包所能装的最优解
            else//装不下
                dp[i][j] = dp[i - 1][j];//装不下和能装下但不拿的情况一样
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

滚动数组

观察上面代码中的循环体。你会发现dp[i][j]永远和dp[i-1]有关系，也就是说该层数据是由上一层数据得到的。
那么我们就可以不用存储之前的数据只用存储上一层数据通过遍历就可以推导出最终结果
那么二维数组可以直接变为一维数组dp[i]
i表示的是背包容积，元素存储的是最优价值。
上代码

for (i = 1; i <= n; i++)
for (j = m; j >= item_w[i]; j–)
dp[j] = max(dp[j], dp[j - item_w[i]] + item_v[i]);

现在解决几个初学者的问题

Q1：思路我懂，代码啥意思？

A1：这里得dp[j]存储的是容积j的最优解，本次循环如果不进行更新那么就代表着上一层的最优解，而当他更新完了之后就会变成本层的最优解，那么上一层的就丢失了，咱们也不需要。
dp[j-item_w[i]]是容积为j-该物体容积的背包最优解。那加上本物体的价值才是将该物品放入背包后的价值

Q2：那你为啥要逆序？

A2：逆序是保证 dp[j - item_w[i]]的数据是上一层的，如果是正序你想想，j-item_w[i]肯定比j小啊，那么他会被先遍历到啊，那他就被更新了，就是本层的数据，就不是咱们要的上一层数据了，所以咱们要进行逆序

Q3：行，大概明白了，那为啥是两层循环？

A3:咱们只是对于dp进行一个空间上的优化，操作顺序还是不变的，循环就不变。如果不知道操作顺序那你得重学0-1背包了，2233娘直呼内行。

多重背包

有大佬的视频你不看？
look！就是这道题的视频讲解。知道上面的你肯定能看懂了。哎嘿那我就偷懒一下喽。