状态定义：\(f_{i,j}\)表示将前\(i\)件物品放入容量为\(j\)的背包中所能获得的最大价值推理：第\(i\)件物品放或不放

方程：\(f_{i,j}=max(f_{i-1,j},f_{i-1,j-C_i}+W_i)\)

$\Updownarrow $

*空间优化：\(f_j\)表示剩余\(j\)的被包能放下的最大价值方程：\(f_j=max(f_j,f_{j-C_i}+W_i)\)(必须逆序枚举\(j\),否则无法满足无后效性) 代码 for(register int i = 1 ; i <= n ; i++){ for(register int j = V ; j >= C[i] ; j--){ f[j] = max(f[j] , f[j - C[i]] + W[i]); } }

转载于:https://www.cnblogs.com/defense/p/11372403.html

相关资源：JAVA上百实例源码以及开源项目