永济微网站建设费用,西安百度推广代理商,现在公司做网站还需要域名吗,做网站的费用进什么科目1、概述 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优#xff08;即最有利#xff09;的选择#xff0c;从而
希望导致结果是最好或最优的算法。 贪心算法的每一步都是基于当前状态下的最优解来选择下一步#xff0c;因此它不能保证全局最优
解#xff0c…1、概述 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优即最有利的选择从而
希望导致结果是最好或最优的算法。 贪心算法的每一步都是基于当前状态下的最优解来选择下一步因此它不能保证全局最优
解只能保证局部最优解。 贪心算法的优点是思路简单、易于实现、时间复杂度较低但缺点是可能得到非全局最优解。
2、应用场景
背包问题给定一组物品每种物品都有自己的重量和价值确定一个总重量不超过背包容量的情况下使得背包中的总价值最大。最小生成树给定一个带权重的无向图求出该图的最小生成树。旅行商问题给定一组城市和每对城市之间的距离求出访问每个城市一次并返回到原点的最短路径。最大匹配问题给定一个字符串和一个模式串求出模式串在字符串中出现的最大匹配长度。0/1背包问题给定一组物品每种物品都有自己的重量和价值确定一个总重量不超过背包容量的情况下使得背包中的总价值最大。找零问题找到最少数量的硬币使它们的总和等于给定的金额。
3、解决背包问题
解决思路
贪心策略在每一步选择当前可用物品中单位价值最高的物品放入背包直到背包容量达到上限。
算法步骤
初始化将物品按照单位价值从大到小排序。遍历排序后的物品列表 如果当前物品的重量小于等于背包容量将该物品放入背包并更新背包的总重量和总价值。如果当前物品的重量大于背包容量跳过该物品。返回最终放入背包的物品和它们的总价值。
元素
物品 重量价值背包 容量可以承受的重量。
选择装入背包的物品价值最大。
代码
package com.ybw.algorithm.greedy.dto;import lombok.AllArgsConstructor;
import lombok.Data;/*** author weixiansheng* version V1.0* className Goods* date 2023/12/22**/
Data
AllArgsConstructor
public class Goods {/*** 商品价格** author: weixiansheng* date: 2023/12/22**/private Integer price;/*** 重量** author: weixiansheng* date: 2023/12/22**/private Integer weight;
}package com.ybw.algorithm.greedy;import com.ybw.algorithm.greedy.dto.Goods;
import org.junit.jupiter.api.Test;import java.util.ArrayList;
import java.util.List;/*** 贪心算法-背包问题** author weixiansheng* version V1.0* className KnapsackProblemTest* date 2023/12/25**/
public class KnapsackProblemTest {/*** methodName: knapsackProblemTest* return: void* author: weixiansheng* date: 2023/12/22**/Testpublic void knapsackProblemTest() {//1、定义物品列表ListGoods goodsList new ArrayList();goodsList.add(new Goods(60, 10));goodsList.add(new Goods(100, 20));goodsList.add(new Goods(120, 30));// 背包的容量int capacity 50;// 输出背包的最大价值System.out.println(maxValue(capacity, goodsList));}private int maxValue(int capacity, ListGoods goodsList) {int totalValue 0;for (Goods goods : goodsList) {if (capacity goods.getWeight()) {totalValue goods.getPrice();capacity - goods.getWeight();} else {totalValue goods.getPrice() * (capacity / goods.getWeight());break;}}return totalValue;}
}运行结果160。全局最优解为220。
总结它不能保证全局最优解只能保证局部最优解。
