贪心算法和背包问题

1、考虑下述背包问题的实例。有5件物品,背包容量为100,每件物品的价值和重量如下表所示,并已经按照物品的单位重量价值从大到小排好序,根据物品单位重量价值大优先的策略装入背包中,则采用了( 贪心 )设计策略。考虑0/1背包问题(每件物品或者全部放入或者全部不装入背包)和部分背包问题(物体可以部分装入背包),求解该实例,得到的最大价值分别为( 430和630 )。

物品编号 价值 重量
1 50 5
2 200 25
3 180 30
4 225 45
5 200 50

本题考查贪心算法和背包问题的知识点。

    贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
    0/1 背包考虑该问题时,只能放入1、2、3号物品,故总价值为430,采用部分背包问题可以将物品拆分,故放1、2、3号物品后还可以放入部分4号物品,故总容量为630。

发表评论

电子邮件地址不会被公开。 必填项已用*标注