TypeScript实现贪心算法与回溯算法

knapSackGreedy(capacity: number, weights: number[], values: number[]): number {
        const n = values.length;
        // 已装入背包的物品总重量
        let load = 0;
        // 已装入背包的物品总价值
        let val = 0;
        for (let i = 0; i < n && load < capacity; i++) {
            // 物品可以完整的放入背包
            if (weights[i] <= capacity - load) {
                // 将物品的价值计入背包已装入物品的总价值
                val += values[i];
                // 将物品的重量计入背包已装入物品的总重量
                load += weights[i];
            } else {
                // 物品无法完整的放入背包，计算能够装入部分的比例
                const r = (capacity - load) / weights[i];
                // 将计算出的物品价值计入背包已装入物品的总价值
                val += r * values[i];
                // 将物品的重量计入背包已装入物品的总重量
                load += weights[i];
            }
        }
        // 返回物品总价值
        return val;
    }

const designSkills = new DesignSkills();
const result = designSkills.minCoinChangeGreedy([1, 5, 10, 25], 8);
console.log(`找零方案: ${result}`);

/**
     * 贪心算法: 背包问题
     * @param capacity 背包容量
     * @param weights 物品重量
     * @param values 物品价值
     */
    knapSackGreedy(
        capacity: number,
        weights: number[],
        values: number[]
    ): { val: number; compose: ({ dart: boolean; scale: number; id: number } | { dart: boolean; id: number })[] } {
        const n = values.length;
        // 存储解决方案
        const compose = [];
        // 已装入背包的物品总重量
        let load = 0;
        // 已装入背包的物品总价值
        let val = 0;
        for (let i = 0; i < n && load < capacity; i++) {
            // 物品可以完整的放入背包
            if (weights[i] <= capacity - load) {
                // 将物品的价值计入背包已装入物品的总价值
                val += values[i];
                // 将物品的重量计入背包已装入物品的总重量
                load += weights[i];
                // 当前物品可以完整放入，将物品编号放入组合方案中
                compose.push({ id: i, dart: false });
            } else {
                // 物品无法完整的放入背包，计算能够装入部分的比例
                const r = (capacity - load) / weights[i];
                // 将计算出的物品价值计入背包已装入物品的总价值
                val += r * values[i];
                // 将物品的重量计入背包已装入物品的总重量
                load += weights[i];
                // 当前物品无法完整放入，将物品编号和可放物品比例放入组合方案中
                compose.push({ id: i, dart: true, scale: r });
            }
        }
        // 返回物品总价值
        return { val: val, compose: compose };
    }

const designSkills = new DesignSkills();
const values = [3, 4, 5],
    weights = [2, 3, 4],
    capacity = 6;
console.log("容量为6的背包其解决方案为：", designSkills.knapSackGreedy(capacity, weights, values));

/**
     *  回溯算法：迷宫老鼠问题
     *
     * @param maze 迷宫
     */
    ratInAmaze(maze: number[][]): number[][] | string {
        // 解决方案
        const solution: number[][] = [];
        for (let i = 0; i < maze.length; i++) {
            solution[i] = [];
            for (let j = 0; j < maze[i].length; j++) {
                solution[i][j] = 0;
            }
        }
        // 寻找路径
        if (this.findPath(0, 0, maze, solution)) {
            // 返回解决方案
            return solution;
        }
        // 无解
        return "此迷宫无解";
    }
    // 寻找路径
    findPath(x: number, y: number, maze: number[][], solution: number[][]): boolean {
        const n = maze.length;
        // 递归基准条件：老鼠走到了迷宫的尽头
        if (x === n - 1 && y === n - 1) {
            // 将最后一个位置标记为路径的一部分
            solution[x][y] = 1;
            return true;
        }
        // 判断老鼠能否安全移动到该位置
        if (this.isSafe(maze, x, y)) {
            // 该位置可以移动，将其标注为可移动
            solution[x][y] = 1;
            // 沿着迷宫的行移动
            if (this.findPath(x + 1, y, maze, solution)) {
                return true;
            }
            // 沿着迷宫的列移动
            if (this.findPath(x, y + 1, maze, solution)) {
                return true;
            }
            // 水平和垂直都无法移动，将这步路径标注为不可移动
            solution[x][y] = 0;
            // 回溯，即将当前层从递归栈中移除，尝试另一种解决方案
            return false;
        }
        // 所有移动方案都尝试完毕，都无法移动，则退出当前递归
        return false;
    }
    // 验证此位置是否能走
    isSafe(maze: number[][], x: number, y: number): boolean {
        const n = maze.length;
        // x和y必须大于等于0且迷宫的第x行y列不能为0老鼠就可以走
        return x >= 0 && y >= 0 && x < n && y < n && maze[x][y] !== 0;
    }

const designSkills = new DesignSkills();
// 迷宫老鼠问题
const RatResult = designSkills.ratInAmaze([
    [1, 0, 0, 0],
    [1, 1, 1, 1],
    [0, 0, 1, 0],
    [0, 1, 1, 1]
]);
console.log(RatResult);

/**
     * 数独解题器
     * 游戏规则：
     *        1. 用数字1~9填满一个9*9的矩阵
     *        2. 矩阵的每行每列都由1～9这九个数字组成，且不能重复
     *        3. 矩阵还包含了3*3的小矩阵，同样需要用这9个数字填满，填充时其值所在的小矩阵中不能有重复的数字
     *        4. 游戏开始前会提供一个数独矩阵，它填了部分数字，未填充部分用0表示
     * @param matrix 数独矩阵
     */
    sudokuSolver(matrix: number[][]): number[][] | string {
        if (this.solveSudoku(matrix)) {
            return matrix;
        }
        return "此问题无解";
    }
    /**
     * 解数独
     * @param matrix 数独
     * @private
     */
    private solveSudoku(matrix: number[][]) {
        // 辅助变量用于描述数独的行和列
        let row: number;
        let col = 0;
        // 检查格子是否为空
        let checkBlankSpaces = false;
        // 寻找空格子
        for (row = 0; row < matrix.length; row++) {
            for (col = 0; col < matrix[row].length; col++) {
                // 检测到空格子，终止内层循环
                if (matrix[row][col] === this.UNASSIGNED) {
                    checkBlankSpaces = true;
                    break;
                }
            }
            // 格子为空终止外层循环
            if (checkBlankSpaces) {
                break;
            }
        }
        // 格子不为空时终止递归
        if (!checkBlankSpaces) {
            return true;
        }
        // 为空格子填充数字，判断其是否满足数独的填充规则
        for (let num = 1; num <= 9; num++) {
            // 如果满足规则，就往空格子填充num
            if (DesignSkills.MatrixIsSafe(matrix, row, col, num)) {
                matrix[row][col] = num;
                // 递归，继续寻找空格子，然后填充
                if (this.solveSudoku(matrix)) {
                    return true;
                }
                // 所有数字都尝试完后，仍然不满足则填充0
                matrix[row][col] = this.UNASSIGNED;
            }
        }
        // 回溯，即将返回到上一个递归栈
        return false;
    }
    /**
     * 校验当前值是否冲突
     * @param matrix
     * @param row
     * @param col
     * @param num
     * @private
     */
    private static MatrixIsSafe(matrix: number[][], row: number, col: number, num: number): boolean {
        // 当num的值不再当前行，不在当前列，不在3*3的小格子中时则表示num不冲突
        return (
            !DesignSkills.usedInRow(matrix, row, num) &&
            !DesignSkills.usedInCol(matrix, col, num) &&
            !DesignSkills.usedInBox(matrix, row - (row % 3), col - (col % 3), num)
        );
    }
    /**
     * 检测当前值是否在矩阵的指定行中
     * @param matrix
     * @param row
     * @param num
     * @private
     */
    private static usedInRow(matrix: number[][], row: number, num: number): boolean {
        for (let col = 0; col < matrix.length; col++) {
            if (matrix[row][col] === num) {
                return true;
            }
        }
        return false;
    }
    /**
     * 检测当前值是否在矩阵的指定列中
     * @param matrix
     * @param col
     * @param num
     * @private
     */
    private static usedInCol(matrix: number[][], col: number, num: number): boolean {
        for (let row = 0; row < matrix.length; row++) {
            if (matrix[row][col] === num) {
                return true;
            }
        }
        return false;
    }
    /**
     * 检测当前值是否在3*3的小矩阵中
     * @param matrix
     * @param boxStartRow
     * @param boxStartCol
     * @param num
     * @private
     */
    private static usedInBox(matrix: number[][], boxStartRow: number, boxStartCol: number, num: number): boolean {
        for (let row = 0; row < 3; row++) {
            for (let col = 0; col < 3; col++) {
                if (matrix[row + boxStartRow][col + boxStartCol] === num) {
                    return true;
                }
            }
        }
        return false;
    }

const designSkills = new DesignSkills();
// 数独解题器
const sudokuGrid = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
];
console.log(designSkills.sudokuSolver(sudokuGrid));