集合:

在前i件物品中,选择总体积不超过j的物品的所有选择方案

属性:

集合中所有选择方案中,价值最大的方案的价值

状态计算:

集合划分为:包含了第i件物品f[i - 1, j - v[i]]+w[i]和不包含第i件物品f[i-1,j]

状态转移方程:

f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])

结果:f[m][n]

可以压缩成一维

for (int i = 1; i <= m; i++) {
	for (int j = n; j >= w[i]; j--) {
		f[j] = max(f[j], f[j - w[i]] + v[i]);
	}
}