【学习笔记】——背包 之01背包
01背包：
01背包之所以叫做01背包，是因为对于每件物品，都只有两种情况：要或不要
例题：01背包
分析：每种物品只有两种情况：要或不要，典型的01背包
状态：f[i][v]:前 i 件物品放在 v 空间内产生的最大价值
推导方程：
当第 i 件物品放时：f[i][j]=f[i-1][j-w[i]]+c[i] (即：前 i-1 件物品放在 （j-第 i 件物品所占空间）时的最大价值 + 第 i 件物品的价值）
不放时：f[i]=f[i-1][j](即：前 i-1 件物品放在 j 空间中的最大值）
又因为要取最大价值，所以：f[i][j]=max(f[i-1][j-w[i]]+c[i],f[i-1][j])
#include
using namespace std;
int n,m;
int f[1000][1000];
int w[100100],c[100100];
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
cin>>w[i]>>c[i];
for(int i=1;i<=n;i++)
for(int j=n;j>=1;j--)
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);
cout< 但这样的时间、空间复杂度均为O（n*v），其中时间复杂度已无法优化，但空间还可以优化
优化方法一：滚动数组
如果仔细看一下方程，不难发现，对于当前的f[i][j]，其实只用到了第 i 行和第 i-1 行
所以，我们可以将f[n][m]定义为f[2][m](n,m均为长量），再定义两个变量：pre、cur（ pre 表示该行的上一行，cur 表示该行）。
但我们怎么更改 pre 与 cur 的值呢？
非常简单：swap(cur,pre) 即可；
#include
using namespace std;
int n,m,cur=1,pre;
int w[100100],c[100100],f[1000][1000];
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>w[i]>>c[i];
for(int i=1;i<=m;i++)
{
swap(cur,pre);
for(int j=n;j>=1;j--)
{
if(j>=w[i])
f[cur][j]=max(f[pre][j],f[pre][j-w[i]]+c[i]);
else
f[cur][j]=f[pre][j];
}
}
cout< 优化方法二：
优化原理同上，不过比上一个更狠：直接压成一维
方程：f[j]=max(f[j],f[j-w[i]]+c[i])
解释：
在更新f[j]之前，f[j]相当于之前的f[i-1] [j]（可以理解为：a=a+3;） 而更新后，f[j]就成了f[i] [j]
所以，必须从后往前更新，否则，方程就成了f[i][j]=max(f[i][j-w[i]]+c[i],f[i-1][v])
代码：
#include
using namesapce std;
int n,m;
int w[100100],c[100100];
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
cin>>w[i]>>c[i];
for(int i=1;i<=n;i++)
for(int j=m;j>=1;j--)
if(j>=w[i])
f[j]=max(f[j],f[j-w[i]]+c[i]);
else
f[j]=f[j-1];
cout<