Java算法之BFS,DFS,动态规划和贪心算法如何实现
本篇内容主要讲解“Java算法之BFS,DFS,动态规划和贪心算法如何实现”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“Java算法之BFS,DFS,动态规划和贪心算法如何实现”吧!
广度优先搜索
广度优先搜索算法是一种遍历或搜索树或图的算法,它从根节点开始搜索并逐层向下扩展,直到找到目标状态或所有节点都被遍历。BFS通常使用队列来实现,它每次将下一个节点放入队列中,直到所有的节点都被访问。
下面是一个Java实现:
public void bfs(Node start) {
Queue<Node> queue = new LinkedList<>();
Set<Node> visited = new HashSet<>();
queue.offer(start);
visited.add(start);
while (!queue.isEmpty()) {
Node node = queue.poll();
System.out.print(node.val + " ");
for (Node neighbor : node.neighbors) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(neighbor);
}
}
}
}
深度优先搜索
深度优先搜索算法是一种遍历或搜索树或图的算法,它从根节点开始递归地遍历所有子树,直到找到目标状态或所有节点都被遍历。DFS通常使用栈来实现,它每次将下一个节点压入栈中,直到所有的节点都被访问。
下面是一个Java实现:
public void dfs(Node node, Set<Node> visited) {
System.out.print(node.val + " ");
visited.add(node);
for (Node neighbor : node.neighbors) {
if (!visited.contains(neighbor)) {
dfs(neighbor, visited);
}
}
}
动态规划
动态规划算法(DP)是一种解决问题的方法,它用来解决重叠子问题和最优子结构问题。DP通常用来解决优化问题,例如最短路径问题、背包问题等。
下面是一个Java实现:
public int knapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= capacity; j++) {
if (weights[i - 1] <= j) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][capacity];
}
贪心
贪心算法是一种解决优化问题的方法,它总是选择当前最优解。与动态规划不同,贪心算法并没有考虑所有的子问题,而是只看当前的最优解。
下面是一个Java实现:
public int knapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
Item[] items = new Item[n];
for (int i = 0; i < n; i++) {
items[i] = new Item(weights[i], values[i]);
}
Arrays.sort(items, (a, b) -> b.valuePerWeight - a.valuePerWeight);
int totalValue = 0;
int remainingCapacity = capacity;
for (Item item : items) {
if (remainingCapacity >= item.weight) {
totalValue += item.value;
remainingCapacity -= item.weight;
} else {
totalValue += item.valuePerWeight * remainingCapacity;
break;
}
}
return totalValue;
}
class Item {
int weight;
int value;
int valuePerWeight;
public Item(int weight, int value) {
this.weight = weight;
this.value = value;
this.valuePerWeight = value / weight;
}
}
相关内容
这些是最新的
热门排行
- THINKPHP5+GatewayWorker+Workerman 开发在线客服系统
- 在手机浏览器网页中点击链接跳转到微信界面的方法
- 尊云网站目录系统 ThinkPHP5网站分类目录程序 v2.2.221011
- CentOS 7安装shadowsock(一键安装脚本)
- AdminTemplate 基于LayUI 2.4.5实现的网站后台管理模板
- 用NW.js(node-webkit)开发多平台的桌面客户端
- PHP生成随机昵称/用户名
- THINKPHP5网站分类目录程序 尊云网站目录系统
- 织梦(DEDECMS)微信支付接口 微信插件
- 基于LayUI开发的 网站后台管理模板 BeginnerAdmin
- 响应式后台网站模板 - AMA.ADMIN
- layuiAdmin后台管理模板 Iframe版
- LayUI 1.0.9 升级 至 LayUI 2.1.4 方法
- 简洁清爽的会员中心模板
- jQuery幸运大转盘抽奖活动代码