算法设计与分析W12-近似算法
近似算法ApproximationAlgorithms近似算法的设计方法u贪心算法ü旅行商问题ü背包问题ü最小顶点覆盖问题u局部搜索(localsearch)u线性规划u随机算法u动态规划u……91最大背包问题（MaximumKnapsack）背包问题ü输入：n个物品的集合U={u1,u2,...,un}，其中物品ui的重量记为w(ui)，价值记为v(ui)，i=1,2,...,n；一个承重为W的背包，ü输出：价值最高的物品子集=:⊆U，且能全部放入背包中，即max{∑;∈=#>?|=:⊆=,∑;∈=#A?≤B}92背包问题的近似算法——贪心算法u贪心策略ü把物品按照重量wi进行降序排序ü把物...
2025-01-13
2.69MB 159 页 0
0
5玖币
渝公网安备50010702506394 | 违法与不良信息举报方式：微信:jiubeiyun2024,QQ:264159069,电话:15523442343,邮箱:jiubeiyun@126.com
