多变量的贪心与动态规划

贪心算法动态规划的主要区别就是前者是通过求局部最优(每个最优解之间没什么联系,也就是每个子问题具有独立性)来解决问题,

                后者是从总体把握求最优(实际还是通过局部最优,只不过最优解之间有联系,即将局部最优值先存在上一节点中,然后最优之间再比较..再存..)

对于多变量的贪心如杭电OJ的作业完成问题(每个作业都有相应学分 m 以及相应拖延时间 t )由于时间相对独立,也就是每天的最优解得出之后并不需要再对每天的最优解进行比较

而对于多变量的动态规划问题如经典的0 1 背包问题(每个物品有相应价值 v 与相应体积 V) 由于容积之间不相对独立,也就是求出每个相同体积的最优解后还要再进行比较

原文地址:https://www.cnblogs.com/MekakuCityActor/p/8244613.html