贪心算法分发糖果python

以下是使用贪心算法分发糖果的Python示例：

def candy(ratings):
    n = len(ratings)
    candies = [1] * n

    # 从左到右遍历，保证右边评分高的孩子获得更多糖果
    for i in range(1, n):
        if ratings[i] > ratings[i-1]:
            candies[i] = candies[i-1] + 1

    # 从右到左遍历，保证左边评分高的孩子获得更多糖果
    for i in range(n-2, -1, -1):
        if ratings[i] > ratings[i+1]:
            candies[i] = max(candies[i], candies[i+1] + 1)

    return sum(candies)

ratings = [1, 0, 2]
print(candy(ratings))  # 输出：5

相关问题

贪心算法解决TSP python

TSP问题是指旅行商问题，即在给定的一些城市之间，求解访问每个城市一次并回到起始城市的最短路径。贪心算法可以用来解决TSP问题，但是只能得到近似最优解，而非精确最优解。

具体来说，贪心算法可以采用以下策略：
1. 选择一个起始城市。
2. 从起始城市开始，每次选择距离当前城市最近的未访问过的城市，并将其加入路径中。
3. 重复步骤2，直到所有城市都被访问过。
4. 将最后一个城市与起始城市相连，形成回路。

下面是一个使用贪心算法解决TSP问题的Python代码示例：

import math

def tsp(points):
    n = len(points)
    visited = [False] * n
    path = [0] * n
    visited[0] = True
    path[0] = 0
    for i in range(1, n):
        min_dist = math.inf
        for j in range(n):
            if not visited[j]:
                dist = math.sqrt((points[j][0] - points[path[i-1]][0])**2 + (points[j][1] - points[path[i-1]][1])**2)
                if dist < min_dist:
                    min_dist = dist
                    path[i] = j
        visited[path[i]] = True
    path.append(0)
    return path

# 示例
points = [(0, 0), (1, 1), (2, 2), (3, 3)]
path = tsp(points)
print(path)  # 输出 [0, 1, 2, 3, 0]

贪心算法tsp问题python

下面是使用Python实现TSP问题的贪心算法：

import math

def tsp(points):
    # 计算两点之间的距离
    def distance(point1, point2):
        return math.sqrt((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2)

    # 计算路径长度
    def path_length(path):
        length = 0
        for i in range(len(path) - 1):
            length += distance(points[path[i]], points[path[i+1]])
        return length

    # 选择下一个要访问的城市
    def choose_next_city(current_city, unvisited_cities):
        next_city = None
        min_distance = float('inf')
        for city in unvisited_cities:
            d = distance(points[current_city], points[city])
            if d < min_distance:
                min_distance = d
                next_city = city
        return next_city

    # 贪心算法
    path = [0]  # 起点为0号城市
    unvisited_cities = set(range(1, len(points)))
    while unvisited_cities:
        next_city = choose_next_city(path[-1], unvisited_cities)
        path.append(next_city)
        unvisited_cities.remove(next_city)
    path.append(0)  # 回到起点
    return path_length(path), path

其中，`points`是一个二维坐标列表，表示每个城市的坐标。函数返回值为最短路径长度和路径。