回顾一下
f[i][j] 所有只考虑前i个物品 且总体积不大于j的所有选法

当前种类的物品，“选了多少个”：
选0个，就是前面物品在当前体积下的最大价值：f[i-1][j]；
选1个，前面物品在去掉当前1个物品体积的最大价值+当前1个物品的价值：f[i-1][j-1v[i]]+1w[i];
选2个，前面物品在去掉当前2个物品体积的最大价值+当前2个物品的价值：f[i-1][j-2v[i]]+2w[i];
不难能推导出 完全背包的动态转移方程 f[i,j]=f[i-1,j-v[i]*k]+w[i]*k (注意k有限制条件的)
将其展开
f[i,j]=max(f[i-1,j],f[i-1,j-v[i]]+W,f[i-1,j-2v[i]]+2W…)
f[i,j-v[i]]=max(f[i-1],j-v[i],f[i-1,j-2v]+w…)
两者相似 从第二项开始每项差一个w
所以f[i,j]=max(f[i-1,j],f[i,j-v]+w) 这样就不用枚举k了

这时我们便发现 二维完全背包和二维01背包非常的相似 其实唯一的区别就是
01背包 f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i])
完全背包 f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i])
便于记忆

[完全背包] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
using namespace std;

const int N=1010;
int n,m,v[N],w[N],f[N][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=0;j<=m;j++)
		{
		    f[i][j]=f[i-1][j];
		    if(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
		}
	}
	cout<<f[n][m]<<endl;
	return 0;
}

完全背包一维就非常简单了 从v[i]开始枚举 不用倒序 把第一维删掉即可

[完全背包一维] [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<iostream>
using namespace std;

const int N=1010;
int n,m,v[N],w[N],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=v[i];j<=m;j++)
	    {
	        f[j]=f[j];
	        f[j]=max(f[j],f[j-v[i]]+w[i]);
	    }
	}
	cout<<f[m]<<endl;
	return 0;
}


我们其实就能发现 一维的话 貌似除了枚举部分 其它都一样？？