组合优化问题 组合优化问题的相关概念、 目标函数（极大化或极小化） 约束条件（解满足的条件） 可行解：搜素空间满足约束条件的解 最优解：使得目标函数达到极大（或极小）的可行解 代价函数 计算位置：搜索树的节点 值：极大化问题是以该点为根的子树所有可行解的值的上界 性质：对极大化问题父节点代价不小于子节点的代价（极小化问题相反） 界 含义：当前得到可行解的目标函数的最大值 初值：极大化问题初值为0（极小化问题为最大值） 更新：得到更好的可行解时 F的值>=B
停止分支回溯父节点的依据： 1.不满足约束条件 2.对于极大化问题，代价函数值小于当前界（对于极小化问题是大于界） 界的更新： 对极大化问题，如果一个新的可行解的优化函数值大于（极小化问题为小于）当前的界，则把界更新为该可行解。 有4种物品，重量和价值已知，背包的重量限制为10. 求得是每个物品应该拿多少
对节点<x1,x2,x3…xk>,估计以该节点为根得子树中可行解得上界按vi/wi，从小到大排序，i=1,2,3,…n代价函数=已经装价值+▲ ▲：还可继续装入最大价值得上界 ▲ =背包剩余容量*vk+1/wk+1（可装） ▲=0(不可装)*
