Thuật toán tham lam giải bài toán siêu chuỗi ngắn nhất

Mô tả vấn đề.

Cho một mảng các chuỗi, hãy tìm chuỗi siêu chuỗi ngắn nhất, tức là chuỗi chứa tất cả các chuỗi và mỗi chuỗi chỉ xuất hiện một lần.

Đầu vào: ["abc", "bcd", "cde"] .

Đầu ra: "abcde" .

Ý tưởng giải quyết vấn đề.

1. Sắp xếp mảng chuỗi đã cho theo chiều dài từ lớn đến nhỏ, ghi dưới dạng chuỗi. 2. Xác định một mảng đã truy cập để ghi lại xem mỗi chuỗi đã được truy cập hay chưa. Các giá trị ban đầu là sai. 3. Xác định một biến result để ghi lại siêu chuỗi ngắn nhất cuối cùng. Giá trị ban đầu là một chuỗi trống. 4. Duyệt mảng chuỗi bắt đầu từ chuỗi đầu tiên: a. Nếu chuỗi hiện tại đã được truy cập, hãy bỏ qua chuỗi đó. b. Thêm chuỗi hiện tại vào kết quả và đặt vị trí tương ứng trong mảng đã truy cập thành true. c. Bắt đầu từ cuối chuỗi hiện tại, tìm hậu tố chung dài nhất trong các chuỗi chưa được truy cập trong mảng chuỗi, thêm nó vào kết quả và cập nhật mảng đã truy cập. 5. Sau khi duyệt tất cả các chuỗi, chuỗi siêu ngắn nhất sẽ được lưu trong kết quả.

mã giả.

                        
                          hàm findShortestSuperstring(strings): // 按照长度从大到小排序 sắp xếp(chuỗi, thứ tự độ dài giảm dần) // 记录每个字符串是否被访问 đã truy cập = new Array(strings.length, false) //存储最短超级字符串 result = "" for i từ 1 đến strings.length: if đã truy cập[i] là đúng: tiếp tục kết quả += chuỗi [i] đã truy cập [i] = true bắt đầu = chuỗi [i]. chiều dài trong khi bắt đầu > 0: maxLen = 0 maxIdx = -1 cho j từ 0 đến strings.length: if đã truy cập[j] là đúng: continue len = commonSuffix(strings[i], strings[j]) if len > maxLen: maxLen = len maxIdx = j nếu maxIdx == -1: ngắt kết quả += strings[j].substring(maxLen) visited[maxIdx] = true start = strings[maxIdx].length trả về kết quả hàm commonSuffix(str1, str2): len1 = str1.length len2 = str2.length len = min(len1, len2) hậu tố = "" cho i từ 1 đến len: nếu str1.substring(len1 - i) == str2.substring(0, i): hậu tố = str2.substring(0, i) trả về hậu tố
                        
                      

Thuật toán tham lam giải bài toán trình tự công việc tối ưu

Mô tả vấn đề.

Có n nhiệm vụ cần hoàn thành và mỗi nhiệm vụ đều có thời điểm bắt đầu và thời gian kết thúc. Cần phải tìm ra trình tự công việc tối ưu để các nhiệm vụ này có thể được hoàn thành một cách suôn sẻ và có thể hoàn thành được nhiều công việc nhất có thể.

Ý tưởng giải quyết vấn đề.

1. Sắp xếp danh sách công việc nhất định theo thời gian kết thúc từ nhỏ đến lớn. 2. Xác định một kết quả có thể thay đổi để ghi lại chuỗi công việc tốt nhất được chọn cuối cùng, ban đầu là một chuỗi trống. 3. Chọn công việc đầu tiên và thêm nó vào kết quả. 4. Duyệt qua danh sách công việc bắt đầu từ công việc thứ hai: a. Nếu thời gian bắt đầu của công việc hiện tại sau thời gian kết thúc của công việc trước đó thì có nghĩa là công việc đó có thể được chọn và thêm vào kết quả. b. Cập nhật công việc trước đó thành công việc hiện tại. 5. Sau khi duyệt qua tất cả công việc, trình tự công việc tốt nhất sẽ được lưu trong kết quả.

mã giả.

                        
                          function findBestJobSequence(jobs): // Sắp xếp theo thời gian kết thúc từ nhỏ đến lớn sắp xếp(công việc, thứ tự tăng dần của thời gian kết thúc) // Lưu trữ chuỗi công việc tốt nhất result = [] result.push(jobs[0]) prevJob = jobs[ 0 ] cho tôi từ 1 đến jobs.length: currJob = jobs[i] if currJob.startTime >= prevJob.endTime: result.push(currJob) prevJob = kết quả trả về currJob
                        
                      

Lưu ý: Ở đây giả định danh sách công việc đầu vào là dữ liệu có cấu trúc tương tự, chứa thông tin về thời gian bắt đầu và thời gian kết thúc của từng công việc, có thể sửa đổi theo nhu cầu thực tế.

Thuật toán tham lam giải bài toán tiếp nhiên liệu tối ưu

Mô tả vấn đề.

Có một ô tô đi trên một con đường, chiều dài đường là L. Dung tích bình xăng của ô tô là C, lúc đầu bình xăng của ô tô trống. Ôtô cần đi từ điểm đầu đến điểm cuối, trong đó sẽ gặp N cây xăng, khoảng cách giữa mỗi cây xăng và điểm xuất phát là d, và lượng nhiên liệu mỗi cây xăng có thể đổ đầy là v. Cần phải tìm ra giải pháp tiếp nhiên liệu tối ưu để ô tô có thể đến đích một cách suôn sẻ với số lần tiếp nhiên liệu ít nhất.

Ý tưởng giải quyết vấn đề.

1. Xác định một bình chứa biến thiên để lưu trữ mức nhiên liệu hiện tại của ô tô, với giá trị ban đầu là 0. 2. Xác định số lượng biến để lưu trữ số lần tiếp nhiên liệu, với giá trị ban đầu là 0. 3. Xác định một biến currentDistance để lưu trữ quãng đường mà ô tô hiện tại đã đạt được, với giá trị ban đầu là 0. 4. Khởi tạo maxHeap heap tối đa để lưu trữ các trạm xăng tùy chọn, được sắp xếp theo lượng tiếp nhiên liệu v. 5. Duyệt qua bộ sưu tập trạm xăng: a. Thêm trạm xăng hiện tại vào heap maxHeap. b. Nếu bình xăng của ô tô không đủ để đến trạm xăng hiện tại và đống maxHeap không trống: - Lấy một trạm xăng ra khỏi đống xăng tối đa maxHeap và ghi là trạm. - Tính toán lượng nhiên liệu cần thiết để đi từ trạm xăng trước đến trạm xăng hiện tại, ghi là requireGas = station.distance - currDistance. - Nếu yêu cầuGas lớn hơn bình xăng của ô tô thì không thể đến được trạm xăng hiện tại và trả về -1. - Thêm Gas cần thiết vào bình dầu của ô tô và thêm 1 vào bộ đếm, cho biết dầu đã được thêm một lần. - Cập nhật khoảng cách hiện tại của xe hiện tại với khoảng cách tới trạm xăng hiện tại. c. Nếu bình xăng của ô tô vẫn không đủ để về đích thì sẽ không thể về đích một cách suôn sẻ và sẽ bị trả về -1. 6. Trả về số đếm, cho biết số lần tiếp nhiên liệu tối thiểu.

mã giả.

                        
                          hàm findOptimalRefueling(stations, L, C): tank = 0 count = 0 currDistance = 0 maxHeap = initializeMaxHeap() cho mỗi trạm trong các trạm: addStationToMaxHeap(maxHeap, station) nếu tank < station.distance - currDistance và !isEmpty(maxHeap): while tank < station.distance - currDistance và !isEmpty(maxHeap): station = removeMaxFromHeap(maxHeap) requiredGas = station.distance - currDistance nếu requiredGas > tank: trả về -1 tank += requiredGas count += 1 currDistance = station.distance nếu tank < station.distance - currDistance: trả về -1 trả về count
                        
                      

Lưu ý: Ở đây giả định bộ trạm xăng đầu vào là dữ liệu có cấu trúc tương tự, chứa thông tin về khoảng cách và khả năng tiếp nhiên liệu của từng trạm xăng, có thể sửa đổi theo nhu cầu thực tế.

Thuật toán tham lam để giải quyết vấn đề tiền xu

Mô tả bài toán thuật toán: Cho một số lượng và một dãy đồng xu có mệnh giá khác nhau, yêu cầu tổ hợp các đồng xu nhỏ nhất để tạo thành số lượng đó và trả về số lượng xu. Giả sử có đủ số lượng mỗi đồng tiền.

Đầu vào và đầu ra mẫu: Đầu vào: số tiền = 11, xu = [1, 2, 5] Đầu ra: 3.

Ý tưởng giải quyết vấn đề: 1. Khởi tạo một số biến để ghi lại số xu cần thiết. 2. Sắp xếp các mảng mệnh giá tiền xu theo thứ tự giảm dần để thuận tiện cho việc lựa chọn tham lam. 3. Duyệt qua mảng tiền xu và ghi lại mệnh giá tiền xu hiện tại là tiền xu. 4. Nếu mệnh giá coin hiện tại nhỏ hơn hoặc bằng số tiền thì thương số chia số tiền theo coin được ghi là numCoins, nghĩa là có thể dùng numCoins coins để bù vào số tiền. - Thêm numCoins để đếm. - Cập nhật số tiền thành số tiền trừ đi mệnh giá của đồng numCoins. 5. Số lần trả lại.

mã giả:

                        
                          hàm coinChange(số lượng, tiền xu) đếm = 0 sắp xếp tiền xu theo thứ tự giảm dần đối với tiền xu trong tiền xu nếu tiền xu <= số lượng thì numCoins = số lượng / tiền xu đếm = số lượng + numCoins số lượng = số lượng - (numCoins * tiền xu) trả về số lượng
                        
                      

Giải thích: Trong bài toán này, đồng xu có mệnh giá lớn nhất được chọn mỗi lần thông qua lựa chọn tham lam. Vì mệnh giá của đồng xu là cố định nên đây là tình huống phù hợp có thể được giải quyết bằng thuật toán tham lam. Vì bắt buộc phải tìm số lượng xu tối thiểu nên chúng ta nên chọn đồng xu có mệnh giá lớn nhất trước tiên. Sau đó giảm dần số tiền cho đến khi số tiền bằng 0. Lưu ý rằng lựa chọn tham lam ở đây có thể không phải là giải pháp tối ưu toàn cục, nhưng trong bài toán này, lựa chọn tham lam có thể thu được giải pháp tối ưu.

Thuật toán tham lam để giải bài toán trò chơi bắn súng

Mô tả vấn đề:

Trong trò chơi bắn súng, người chơi cần bắn một số quả bóng bay có màu sắc khác nhau. Mỗi quả bóng có một giá trị điểm được chỉ định và bán kính nổ. Giả sử điểm bắn của người chơi là tọa độ (x, y) trên mặt phẳng hai chiều. Khi người chơi bắn một viên đạn đến điểm này, viên đạn sẽ tạo thành một phạm vi nổ tập trung vào điểm này. Bất kỳ quả bóng nào đi qua bán kính vụ nổ sẽ bị bắn trúng. Điểm của người chơi bằng tổng điểm của tất cả các quả bóng bay trúng. Bây giờ, với tọa độ, giá trị điểm và bán kính nổ của một số quả bóng bay, cần xác định người chơi nên chọn điểm bắn nào để ghi điểm tối đa.

Mẫu đầu vào và đầu ra:

Đầu vào: Danh sách bong bóng: [(1,2,3), (2,5,4), (3,1,2), (4,9,5)] Mô tả: [ Tọa độ của bong bóng (x, y ), Giá trị điểm, bán kính vụ nổ].

Kết quả: Điểm tối đa: 14 (bằng cách đánh vào hai quả bóng (1,2) và (2,5)).

Ý tưởng giải quyết vấn đề:

1. 创建一个空集合visited来保存已击中的气球。 2. 遍历气球列表，每次选择得分值最高的气球，并将其加入visited集合。 3. 定义一个函数is_overlap用来判断两个气球是否有重叠的爆炸范围。两个气球的距离小于等于它们的爆炸半径之和时，表示它们有重叠。 4. 在遍历气球列表的过程中，检查当前气球与visited集合中的气球是否有重叠的爆炸范围。若有重叠，则选择得分值更高的气球加入visited集合，替代原有的气球。 5. 遍历完所有气球后，visited集合中保存的即为玩家应该击中的气球。 6. 计算visited集合中气球的得分值之和，即为最大得分值.

mã giả:

                        
                          function is_overlap(ball1, ball2): // 判断两个气球是否有重叠的爆炸范围 distance = sqrt((ball1.x - ball2.x)^2 + (ball1.y - ball2.y)^2) return distance <= ball1.radius + ball2.radius function shooting_game(balloons): visited = set() max_score = 0 for i in range(len(balloons)): if i not in visited: // 未被击中过的气球 visited.add(i) max_score += balloons[i].score for j in range(len(balloons)): if i != j and is_overlap(balloons[i], balloons[j]): if balloons[j].score > balloons[i].score: visited.remove(i) max_score -= balloons[i].score visited.add(j) max_score += balloons[j].score return max_score // 测试 balloons = [(1,2,3), (2,5,4), (3,1,2), (4,9,5)] max_score = shooting_game(balloons) print(max_score)
                        
                      

贪心算法解决数组重组问题

算法问题描述:

给定一个整数数组nums，现在需要将数组中的元素重新排列，使得任意两个相邻的元素之间的差的绝对值尽可能大。请实现一个函数，返回重组后的数组。注意，重组后的数组可能不是唯一的，只需返回任意一个满足条件的数组即可.

Mẫu đầu vào và đầu ra:

输入：[1, 2, 3, 4, 5] 输出：[1, 3, 2, 4, 5] 。

Ý tưởng giải quyết vấn đề:

1. 对数组进行排序，从小到大。 2. 创建一个空的结果数组result[]，并将排序后的第一个元素nums[0]加入result[]。 3. 从第二个元素开始遍历排序后的数组，逐个将元素插入result[]。 4. 奇数索引位置上的元素应该尽量取较大的值，所以将当前元素插入result[]的奇数索引位置。 5. 偶数索引位置上的元素应该尽量取较小的值，所以将当前元素插入result[]的偶数索引位置。 6. 遍历完所有元素后，result[]即为重组后的数组.

mã giả:

                        
                          function rearrange_array(nums): sorted_nums = sort(nums) result = [] result.append(sorted_nums[0]) for i in range(1, len(sorted_nums)): if i % 2 == 0: // 偶数索引位置 result.insert(i, sorted_nums[i]) else: // 奇数索引位置 result.append(sorted_nums[i]) return result // 测试 nums = [1, 2, 3, 4, 5] rearranged_nums = rearrange_array(nums) print(rearranged_nums)
                        
                      

输出：[1, 3, 2, 5, 4] 。

贪心算法解决左右两边元素和相等问题

算法问题描述:

给定一个整数数组nums，现在需要判断是否存在一个索引，使得索引左边的元素之和等于索引右边的元素之和。如果存在这样的索引，返回True；否则，返回False.

Mẫu đầu vào và đầu ra:

输入：[1, 7, 3, 6, 5, 6] 输出：True 。

Ý tưởng giải quyết vấn đề:

1. 遍历数组，计算数组中所有元素的和，得到总和total。 2. 初始化左侧元素之和left_sum为0。 3. 从左到右遍历数组，每次将当前元素加入左侧元素之和left_sum，同时将总和total减去当前元素。 4. 在遍历的过程中，检查左侧元素之和left_sum是否等于右侧元素之和total减去当前元素的值。若相等，表示存在满足条件的索引，返回True。 5. 若遍历完所有元素后仍未找到满足条件的索引，则返回False.

mã giả:

                        
                          function equal_sum(nums): total = sum(nums) left_sum = 0 for i in range(len(nums)): total -= nums[i] // 将总和减去当前元素 if left_sum == total: return True left_sum += nums[i] // 将当前元素加入左侧元素之和 return False // 测试 nums = [1, 7, 3, 6, 5, 6] has_equal_sum = equal_sum(nums) print(has_equal_sum)
                        
                      

输出：True 。

贪心算法解决图着色问题

算法问题描述 :

给定一个无向图，图的顶点由一个整数标识，图的边由一个无序的顶点对表示。要求为图的每个顶点分配一个颜色，同时要求相邻的顶点不能有相同的颜色。现在需要设计一个算法，使用贪心算法解决图着色问题，即找到符合要求的最小颜色数量.

Vertices: [1, 2, 3, 4, 5, 6] Edges: [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5), (5, 6)] 。

样例输入 。

graph = {     1: [2, 3],     2: [1, 4],     3: [1, 4],     4: [2, 3, 5],     5: [4, 6],     6: [5] } 。

输出：3 。

解题思路： 1. 创建一个字典colors，用于存储每个顶点的颜色值。初始时，将所有顶点的颜色初始化为-1，表示未分配颜色。 2. 对图中的每个顶点进行遍历，对于每个顶点v，执行以下操作：    1) 创建一个集合used_colors，用于存储v的邻接顶点已经使用的颜色值。    2) 遍历v的邻接顶点，将颜色值加入到used_colors集合中。    3) 遍历颜色值1到无穷大的整数，找到一个未被used_colors集合包含的最小整数，将此整数作为v的颜色值。 3. 返回字典colors中颜色值的种类数量.

mã giả:

                        
                          function graphColoring(graph): colors = {} // 创建一个字典，存储每个顶点的颜色 for each vertex v in graph: used_colors = set() // 创建集合，存储v的邻接顶点已分配的颜色值 for each adjacent_vertex in v.adjacent_vertices: if colors[adjacent_vertex] != -1: // 如果邻接顶点已分配颜色 used_colors.add(colors[adjacent_vertex]) for color in range(1, infinity): // 从1到无穷大的整数 if color not in used_colors: // 找到一个未被邻接顶点使用的最小颜色 colors[v] = color break return number of distinct colors in colors
                        
                      

其中，graph表示输入的无向图，每个顶点的颜色值存储在字典colors中。最后，返回colors中不同颜色值的数量.

  。

最后此篇关于【技术积累】算法中的贪心算法【三】的文章就讲到这里了,如果你想了解更多关于【技术积累】算法中的贪心算法【三】的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。