0-1背包的运算规则

假设题目

假设5个物品，背包总重量为20，想求价值最大；

下面是5个物品的重量和价值
1 6
2 5
3 8
5 15
3 3

第一步：先初始化图标

 第二步：运算规则的解释

先把物品1和2填了再解释

 我们直接看第二个物品那一行是怎么回事

坐标（3，2）怎么回事  ： 此时背包才为1，而物品的重量却有2，我们装不下物品2，只能看之前装的物品1的重量。

坐标（3，3）怎么回事  ： 此时背包为2，也是可以装的下物品2了，直接比较装物品2价值高还是之前物品1价值高，这里物品1价值更高

坐标（3，4）怎么回事  ： 此时背包为3，不仅可以装的下物品2也可以装的下物品1，也算是富裕了，直接全部拿下。拉满！

这里依旧，这里注意一下，比如坐标（4，5）14这里，为什么框了个3*2的框

长为2是因为背包剩余容量为1，加上初始化的1正好为2，宽为3是因为我们在物品3之前已经完成了2次物品的操作，加上初始化的1正好为3。

最后总结一下吧

坐标（5，6）为什么是15，因为装物品4的价值15 比 之前所有物品装的总价值14都要牛逼，所以为15。

坐标（5，7）为什么是21，剩余背包容量为1，加上初始化的1，长为2，之前以前完成了3次物品操作，加上初始化的1，框为4，所以框出4*2的框，这里即可以装的下牛逼的 5重量 15价值 的物品4，也可以装的下唯一真神 1重量 6价值 的物品1，因此为21；

 第三步：代码

#include <bits/stdc++.h>
using namespace std;int main(){int N,V;cin >> N >> V; //N为物品总数，V为背包的容量vector<int> dp(V+1,0);for(int i=0;i<N;i++){int w,v; //w是物品重量，v是物品价值cin >> w >> v;//倒序更新dp数组，避免重复使用物品for(int j=V;j>=w;j--){dp[j] = max(dp[j],dp[j-w] + v);}for(auto &p:dp){cout << p << " ";}}cout << dp[V] << endl; //最后一位即是最终答案}

也可以看一下 真正的输出过程

 第四步：你真的会了吗？？？

 恭喜你已经学会了01背包，下面做个题试试吧！

小 K 有 N 项工作等待完成，第 i 项工作需要花 ti​ 单位时间，必须在 di​ 时刻或之前完成，报酬为 pi​。假设小 K 工作时刻从 0 开始，且同一时刻只能做一项工作、工作一旦开始则不可中断或切换至其他工作，请你帮小 K 规划一下如何选择合适的工作，使小 K 可以获得最多的报酬。

输入格式:

输入第一行是一个正整数 T (≤5)，表示数据的组数。

接下来有 T 组数据，每组数据第一行是一个正整数 N (≤5000)，表示待完成工作的数量。接下来的 N 行，每行三个非负整数 ti​、di​、pi​ (均 ≤5000；1≤i≤N)，表示第 i 项工作需要花费的时间、截止时间以及报酬。

输出格式:

对于每组数据，输出小 K 能获得最多的报酬是多少。

输入样例:

3
5
1 2 50
3 3 100
1 5 1
3 2 5000
4 5 30
5
1 2 50
3 3 20
1 5 1
3 2 5000
4 5 30
5
1 2 50
3 3 100
1 5 1
3 2 5000
5 5 800

输出样例:

101
80
800

 答案：

#include <bits/stdc++.h>
using namespace std;struct Job{int time,deadtime,value;
};int main(){int T;cin >> T;while(T--){int N;cin >> N;vector<Job> job(N);int maxDeadline = 0;for(int i=0;i<N;i++){cin >> job[i].time >> job[i].deadtime >> job[i].value;maxDeadline = max(maxDeadline, job[i].deadtime);}//按截止时间排序（从小到大），若相同按报酬从大到小排序sort(job.begin(),job.end(),[](const Job &a,const Job &b){if(a.deadtime == b.deadtime) a.value > b.value;return a.deadtime < b.deadtime;});//下面开始套公式,dp[i]表示时刻 i 能获得的最大报酬vector<int> dp(maxDeadline + 1,0);for(const auto &p : job){for(int j=p.deadtime;j>=p.time;--j){dp[j] = max(dp[j],dp[j-p.time] + p.value);}}int maxvalue = *max_element(dp.begin(),dp.end());cout << maxvalue << endl;}return 0;
}