题目来源于背包九讲以及https://www.bilibili.com/video/av33930433?p=2以及https://www.acwing.com/problem/content/2/
先来看01背包和完全背包，这两个作为最基础的可以进行对比
01背包：物体只能被选一次或者不选
完全背包：物体可以选无限次
先定义二维f[i][v]为前i件物品，在不大于v空间下的最大价值
一般题目要求有两种 1.不要求装满整个背包 2.恰好装满整个背包
1.不要求装满整个背包：全部初始值定义为0，f[n][v]可以由f[m][0]进行转移所得，f[n][v]即最大值
如果只有f[0][0]定义为0，其他f[i][0]定位为-INF的话，那么max(f[n][0],...f[n][v])才是结果
2.恰好装满整个背包
那对应上面的，只有f[0][0]定义为0，其他f[i][0]定位为-INF，f[n][v]是最后的结果
所以一般两种问题，选取初始化方式不一样。
然后回到01背包和完全背包，01背包二维转移方式如下
for i : n 物体转移
for j: v[i] V 容量转移
f[i][j]= max(f[i-1][j],f[i-1][j-v[i]]+w[i])
一般就这么写，二维的表示
然后经常默认空间优化到一维，上式中f[i][j]由f[i-1][j-v[i]推到的，如果直接去掉一维，那么f[j]由f[j-v[i]推到，但按从小到大的顺序，这个表达的是f[i][j]由f[i][j-v[i]推倒的，因为f[i][j-v[i]先更新。。所以容量转移需要从大到小进行遍历。
01背包一维转移方式如下
for i : n 物体转移
for j: V v[i] 容量转移
f[j]= max(f[j],f[j-v[i]]+w[i])
然后是完全背包，完全背包就是可以选无限次。
完全背包一维转移方式如下
for i : n 物体转移
for j:v[i] V 容量转移
f[j]= max(f[j],f[j-v[i]]+w[i])
就第二维反了过来，意思就是f[i][j]可以由f[i][j-v[i]推到到，即可以从f[i][j-v[i]-v[i]]推倒的，即可以取无限次。。。
两道题代码如下：
#include<bits/stdc++.h>
using namespace std;
int n,v;
const int N=1005;
int f[N];
int main()
{
int a,b;
cin>>n>>v;
for(int i=0;i<n;i++)
{
cin>>a>>b;
for(int i=v;i>=a;i--)
{
f[i]=max(f[i],f[i-a]+b);
}
}
cout<<f[v]<<endl;
}
#include<bits/stdc++.h>
using namespace std;
int n,v;
const int N=1005;
int f[N];
int main()
{
int a,w;
cin>>n>>v;
for(int i=0;i<n;i++)
{
cin>>a>>w;
for(int j=a;j<=v;j++)
{
f[j]=max(f[j],f[j-a]+w);
}
}
cout<<f[v]<<endl;
}
接下来是多重背包，多重背包是01背包的扩展版，每一个物品可以选c次，多了一维，然后可以直接加一个循环，变成O(N^3)的算法复杂度。
多重背包一维转移方式如下//O(N^3)
for i : n 物体转移
for j: V v[i] 容量转移
for k: 0:min(j/v[i],c)
f[j]= max(f[j],f[j-kv[i]]+kw[i])
#include<bits/stdc++.h>
using namespace std;
int n,v;
const int N=1005;
int f[N];
int main()
{
cin>>n>>v;
int a,w,s;
for(int i=0;i<n;i++)
{
cin>>a>>w>>s;
for(int j=v;j>=a;j--)
{
for(int k=0;k<=min(j/a,s);k++)
f[j]=max(f[j],f[j-k*a]+k*w);
}
}
cout<<f[v]<<endl;
}
但数据比较大的时候，就需要优化一下了，下面给出两种优化，一种是二进制拆分，第二种是单调队列优化。
二进制优化，把s件物品分成1,2,4,8,16...s-*这样的件数，把O(n）的复杂度降到O(logn)
#include<bits/stdc++.h>
using namespace std;
int n,v;
const int N=2005;
int f[N];
vector<pair<int,int>> g;
int main()
{
int a,w,s;
cin>>n>>v;
for(int i=0;i<n;i++)
{
cin>>a>>w>>s;
for(int j=1;j<=s;j*=2)
{
g.push_back(make_pair(j*a,j*w));
s-=j;
}
if(s>0)
g.push_back(make_pair(s*a,s*w));
}
int m=g.size();
for(int i=0;i<m;i++)
for(int j=v;j>=g[i].first;j--)
{
f[j]=max(f[j],f[j-g[i].first]+g[i].second);
}
cout<<f[v]<<endl;
}
单调队列优化是更好的办法。
单调队列就是维护一个具有单调性的队列，递增或者递减，可以在O(n)复杂度维护一个序列的最值问题,用于之前滑动窗口那道题,
这道题因为f[j]只能由f[j-kv[i]]转移所得，即f[j-v[i]]，f[j-2v[i]]等推到，也就是这些数对v的取模都是一样的，
混合背包：有的物品符合01背包的规则，有的物品符合完全背包的规则，还有的物品符合多重背包的规则
二维费用的背包问题：有两个条件的限制，比如重量限制和容量限制
