第一题：分隔等和子集
等下做
acwing【特别注意常用的输入输出】[看到01:11：32]
【重点动态规划（必考）+DFS+贪心】
第五章 动态规划（一）
背包问题：（ps:我这里的小写v一般指的是value，w一般指weight）
N个物品，v[i],w[i]，每个物品最多用0次，容量为V的背包，价值max
0-1背包【每件物品最多用1次】
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];
}完全背包【每件物品无限个】
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;
}