2023.3.19

01背包和完全背包

01背包

有N个背包，第i个物品的价值为v[i],重量为w[i]。选一些物品装到容器为C的背包中，使得背包内物品在总重量不超过C的前提下价值尽量大。

P1048

f[i][j]:取前i中物品，背包容量为j，能取到的最大价值

• 0：不拿
• 1：拿

$$
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])\
第二种情况：j\ge w[i]
$$

边界条件：f[0][j]=f[i][0]=0

//边界条件
for(int i=0;i<n;i++)f[i][0]=0;//n个物品
for(int j=0;j<m;j++)f[0][j]=0;//m容量

当我只有一个物品的时候，背包容量不管是多少，那么取到的最大价值都是value。

• f[i-1][j]:不要第i个物品
• f[i-1][j-w[i]]+v[i]:要第i个物品