01背包是重中之重 是其它所有背包的铺垫
01背包 n种物品 每种只有一个
完全背包 n种物品 每种无限个
多重背包 n种物品每种个数不一样

f[i][j] 下标0到i的物品任取 放到容量为j的背包里

01背包 每种物品仅有一件 可以选择放或者不放
只考虑第i件物品
1.如果体积超了 那么一定就是f[i-1][j]
2.如果不放 容量价值不变 转化为前i-1件物品放入容量为j的背包最大价值f[i-1][j]
3.放了之后 容量减重量 价值增加f[i-1][j-w[i]]+v[i]
max(f[i-1][j],f[i-1][j-w[i]]+v[i])就是对于第i件物品的最优解

f数组的初始化
f[i][j]
对应表格如下
0 1 2 3 4
0 a b c d e
1 f g h i j
2 k l m n o

i即f[1][3]
由递推公式 一定是由左上角递推得到的 那么第一列第一行一定要初始化
背包容量为0 价值一定为0 所以第一列初始化为0
除此之外b一定要初始化为0 不然递推会出错 其它的非0下标不用初始化 均会被覆盖

[01背包二维] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]; //注意由表格 物品从1开始遍历 体积从0 
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            if(j>=v[i])  f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    cout<<f[n][m]<<endl;
}


1.f[j]与f[i][j]中j意思相同 表示容量为j的背包能装的最大价值
2.二维中递推公式是max(f[i-1][j],f[i-1][j-w[i]]+v[i]) 放与不放取最大值
在二维中不放物品是f[i-1][j] 则在一维中 不放物品 重量没变化 价值也没变化 就直接将上一层数据拷贝下来没有变化 所以还是f[j]
如果放物品 那么一维中需要把重量减下去 价值加上 则是f[j-w[i]]+v[i]

为什么从v[i]开始？
因为物品体积大了肯定装不了 那么重量价值无变化 直接拷贝

为什么二维不用倒序 一维必须倒序呢?
例如你现在背包容量为10 g[10] 有一个重量6 价值9的东西
如果不装 例 g[10]=g[10] 因为还是取的之前的值 左边是现在更新的 右边是上一轮循环的
如果装 g[4]+9 这时候便是对应f[i-1][j-v[i]]+w[i] 此时的g[4]便是上一个循环里的g[4]
但如果从前往后循环 在你给g[10]赋值之前 g[4]已经更新了！ g[4]状态不同步 g[4]一定偏差了

[01背包一维优化内存] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--) 
        {
            //f[j]=f[j]; 恒等变换后是恒等式可省略
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m]<<endl; //优化成一维了当然是f[m]
}