首页 > 代码库 > knapsack problem 背包问题 贪婪算法GA

knapsack problem 背包问题 贪婪算法GA

knapsack problem 背包问题贪婪算法GA

技术分享

技术分享

         给点n个物品,第j个物品的重量,价值,背包的容量为。应选哪些物品放入包内使物品总价值最大?

规划模型

 max

s.t.

贪婪算法(GA)

 

1、按价值密度从大到小依次放入包内直到放不下,设此时放了s个物品

2、将所得价值与最大价值()所比较,取最大的作为输出

贪婪算法与最优解竞争比(近似比)为

证明:

 

knapsack problem 背包问题 贪婪算法GA