knapsack problem 背包问题贪婪算法GA
给点n个物品，第j个物品的重量，价值，背包的容量为。应选哪些物品放入包内使物品总价值最大？
规划模型
max
s.t.
贪婪算法（GA）
1、按价值密度从大到小依次放入包内直到放不下，设此时放了s个物品
2、将所得价值与最大价值（）所比较，取最大的作为输出
贪婪算法与最优解竞争比（近似比）为
证明：
knapsack problem 背包问题贪婪算法GA
给点n个物品，第j个物品的重量，价值，背包的容量为。应选哪些物品放入包内使物品总价值最大？
规划模型
max
s.t.
贪婪算法（GA）
1、按价值密度从大到小依次放入包内直到放不下，设此时放了s个物品
2、将所得价值与最大价值（）所比较，取最大的作为输出
贪婪算法与最优解竞争比（近似比）为
证明：