贪心算法求组合问题，跳马问题

### 贪心算法应用于组合问题

对于组合优化问题，贪心策略通过一系列的选择来构建解，在每一步都做出局部最优选择，期望最终获得全局最优解。然而需要注意的是，并不是所有的组合优化问题都能通过贪心法得到最佳解决方案[^1]。

例如在一个典型的背包问题变种中，如果目标是在不超过容量的情况下最大化物品总价值，则可以按照单位重量的价值对物品排序并依次选取直到无法再加入新的整件商品为止。但是这种方法并不总是能找到绝对最好的方案，因为有时候少量高单价的小物件可能比一件大而便宜的东西更优。

def knapsack_greedy(weights, values, capacity):
    items = sorted(zip(values, weights), key=lambda item: item[0]/item[1], reverse=True)
    total_value = 0
    remaining_capacity = capacity
    
    for value, weight in items:
        if remaining_capacity >= weight:
            total_value += value
            remaining_capacity -= weight
            
    return total_value

### 使用贪心方法求解骑士巡游问题

棋盘上的骑士巡游问题是经典的图论挑战之一，其中涉及到遍历整个棋盘而不重复访问任何格子。采用Warnsdorff启发式的贪心方式能够有效地处理这个问题——即每次移动到具有最少后续可行位置的那个方格上[^2]。

具体实现如下所示：

import numpy as np

N = 8 # Standard Chessboard Size
moves_x = [2, 1, -1, -2, -2, -1, 1, 2]
moves_y = [1, 2, 2, 1, -1, -2, -2, -1]

def is_valid_move(x, y, board):
    return (x >= 0 and y >= 0 and x < N and y < N and board[x][y] == -1)

def get_next_moves_count(board, cur_x, cur_y):
    count = 0
    for i in range(8):
        next_x = cur_x + moves_x[i]
        next_y = cur_y + moves_y[i]
        if is_valid_move(next_x, next_y, board):
            count += 1
    return count

def solve_knights_tour():
    sol = [[-1]*N for _ in range(N)]
    
    move_x = [2, 1, -1, -2, -2, -1, 1, 2]
    move_y = [1, 2, 2, 1, -1, -2, -2, -1]

    pos = 1
    sol[0][0] = 0

    if not knights_tour_util(sol, 0, 0, move_x, move_y, pos):
        print("Solution does not exist")
    else:
        show_solution(np.array(sol))

def knights_tour_util(sol, cur_x, cur_y, move_x, move_y, pos):
    if pos == N * N:
        return True
        
    min_deg_idx = -1
    c_min = float('inf')
    
    for i in range(8):  
        next_x = cur_x + move_x[i]
        next_y = cur_y + move_y[i]
        
        if is_valid_move(next_x, next_y, sol):
            cnt = get_next_moves_count(sol, next_x, next_y)
            
            if cnt < c_min:
                min_deg_idx = i
                c_min = cnt
                
    if min_deg_idx != -1:
        sol[cur_x][cur_y] = pos
        
        if knights_tour_util(sol, cur_x + move_x[min_deg_idx],
                             cur_y + move_y[min_deg_idx],
                             move_x, move_y, pos + 1):
            return True
            
        sol[cur_x][cur_y] = -1
        
    return False

def show_solution(matrix):
    print("Knight's Tour Solution:")
    print(matrix)


solve_knights_tour()