【计算机算法设计与分析】——5.5 0/1背包问题

说明:

  通过以上的公式向后推倒可以得出每一步的可能情况,再根据约束条件从后往前确定解向量,很明显这样的公式推导十分繁琐,随着问题规模的扩大,分支和情况将十分复杂。

那么现在用图解法来简化这种计算推到形式:

从这个图现在好像只能看出当X=6时,函数值=6,即M=6时,最优总效益值为6。

那么这个图还有没有反应其他的信息呢?我们现在引入一个“序偶”的概念:

所以图解法还能从中直接看出最后阶段的分段函数关系

那么还有什么其他的信息吗?

(辅助概念如下)

 

(不启发,用序偶)

原文地址:https://www.cnblogs.com/chihaoyuIsnotHere/p/9836862.html