首页 > 代码库 > knapsack problem 背包问题 贪婪算法GA
knapsack problem 背包问题 贪婪算法GA
knapsack problem 背包问题贪婪算法GA
给点n个物品,第j个物品的重量,价值,背包的容量为。应选哪些物品放入包内使物品总价值最大?
规划模型
max
s.t.
贪婪算法(GA)
1、按价值密度从大到小依次放入包内直到放不下,设此时放了s个物品
2、将所得价值与最大价值()所比较,取最大的作为输出
贪婪算法与最优解竞争比(近似比)为
证明:
knapsack problem 背包问题 贪婪算法GA
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。