第一题：分隔等和子集
等下做
acwing【特别注意常用的输入输出】[看到01:11：32]
【重点动态规划（必考）+DFS+贪心】
第五章 动态规划（一）
背包问题：（ps:我这里的小写v一般指的是value，w一般指weight）
N个物品，v[i],w[i]，每个物品最多用0次，容量为V的背包，价值max
0-1背包【每件物品最多用1次】
2. 01背包问题 - AcWing题库
f(i,j) 表示总重量<=j，只从前i个物品选的价值max
f(i,j) = max{含i，不含i} = max( f(i-1,j-w[i]) + v[i] , f(i-1,j) )
代码：
错因：for循环的时候i和j弄晕了，i是前i个物品（包括第0个），j是总重量，从1开始算
初始化f[0][j]的时候应该是只要j>=w[0]即可
#include<iostream>
#include<algorithm>using namespace std;int main(){int N;//物品int V;//背包重量cin>>N>>V;vector<int>w(N);//体积vector<int>v(N);//价值for(int i = 0;i<N;i++){cin>>w[i];cin>>v[i];}vector<vector<int>> f(N,vector<int>(V+1));// 初始化第 0 行for (int j = 0; j <= V; j++) {if (j >= w[0]) {f[0][j] = v[0];}}for(int i = 1;i<N;i++){//物品for(int j =1;j<=V;j++){f[i][j] = f[i-1][j];if(j>=w[i]){f[i][j] = max(f[i][j],f[i-1][j-w[i]]+v[i]);}}}cout<<f[N-1][V];}进阶：一维dp
因为f[i]仅仅与f[i-1] 有关，所以可以变成一维数组f[j] 重量<=j的max价值，
就是相当于也是遍历i,遍历j，但是不需要每一个i对应的f都存下来，因为遍历的时候前一个还没有被后一个覆盖
其中，如果直接：f[j] = max(f[j],f[j-w[i]]+v[i]);其实比较的是f[i][j]和f[i][j-w[i]],和预期不符
因此j倒过去遍历，这个好妙！！！！！
#include<iostream>
#include<algorithm>using namespace std;int main(){int N;//物品int V;//背包重量cin>>N>>V;vector<int>w(N);//体积vector<int>v(N);//价值for(int i = 0;i<N;i++){cin>>w[i];cin>>v[i];}vector<int> f(V+1);// 初始化第 0 行for (int j = 0; j <= V; j++) {if (j >= w[0]) {f[j] = v[0];}}for(int i = 1;i<N;i++){//物品for(int j =V;j>=w[i];j--){//f[i][j] = f[i-1]f[j] = max(f[j],f[j-w[i]]+v[i]);//这里如果直接：f[j] = max(f[j],f[j-w[i]]+v[i]);//其实比较的是f[i][j]和f[i][j-w[i]],和预期不符}}cout<<f[V];}完全背包【每件物品无限个】
3. 完全背包问题 - AcWing题库
f[i][j] 同样表示从前i个物品取，总重量<=j
递推公式【就像集合划分一样，不重不漏】：f[i][j] = max( f[i-1][j] , f[i-1][j - k*w[i]]+k*v[i])【k>=0 && k<=V/w[i]】
即max（红框） = f[i,j-v] +w
递推公式升级版：f[i,j] = max(f[i-1,j] , f[i,j-w[i]]+v[i])
对比两个背包：
优化成一维：
f[j] = max( f[j] , f[j-v]+w](这次不需要倒着遍历j
小插曲：这个代码写得，都无语，对i=0的处理，要不然是没加continue,要不然是if的对 i==0的条件限制不全，一部分还是会有f[-1]（见注释）
还是初始化vector<vector<int>>f(N+1,vector<int>(V+1,0))好一点
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;int main() {int N; // 物品数量int V; // 背包容量cin >> N >> V;vector<int> w(N); // 物品体积vector<int> v(N); // 物品价值for (int i = 0; i < N; i++) {cin >> w[i]>> v[i];}vector<vector<int>> f(N, vector<int>(V + 1, 0));// 动态规划//多重f[i,j] = max( f[i-1,j],f[i,j-w]+v)for (int i = 0; i < N; i++) {for (int j = 0; j <= V; j++) {// if(i == 0 && j>=w[0]){// int num = j/w[0];// f[0][j] = num*v[0];// continue;// }else{// f[0][j] = 0;// continue;// }if(i == 0){if(j>=w[0]){int num = j/w[0];f[0][j] = num*v[0];}continue;}f[i][j] = f[i-1][j];//为啥在里面初始化，因为j<w[i]也要有值if(j>=w[i])f[i][j] = max(f[i][j], f[i][j -w[i]]+v[i]); // 选择 k 个当前物品}}cout << f[N - 1][V] << endl;return 0;
}优化版：就挺无语的，遍历改成了i= 1开始，但是前面读取w和v还是从0 开始，但是输出f[v]，输出的是131985？，最后一个是8emmmmm
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;int main() {int N; // 物品数量int V; // 背包容量cin >> N >> V;vector<int> w(N+1); // 物品体积vector<int> v(N+1); // 物品价值for (int i = 1; i <= N; i++) {cin >> w[i]>> v[i];}vector<int> f(V + 1, 0);int j = 0;// 动态规划//多重f[i,j] = max( f[i-1,j],f[i,j-w]+v)for (int i = 1; i <= N; i++) {for (j = w[i]; j <= V; j++) {f[j] = max(f[j], f[j-w[i]]+v[i]); // 选择 k 个当前物品}}cout << f[V] << endl;return 0;
}