Question

01背包问题与贪心法的区别

小弟刚刚学DP的问题,以前也接触过贪心法,有点弄混了,什么样的题面用贪心法作,什么样的题用0-1背包问题作,求指导

Answer 1

贪心法是每一步的最优解就是整体的最优解。
0-1背包是属于动态规划，每一步的解不一定导致整体的最优解。

对于你问
“什么样的题用0-1背包问题作”
就是需要你自己做题来体会了。
如果全局的最优解可以用分布的最优解求出来，就用贪心，
如果不是，就动态规划（0-1背包属于这类）。

合并果子问题（可以自己去网上找哈~）就是典型的贪心，
0-1背包问题就属于典型动态规划。