集合:
在前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]);
}
}