算法母题

0-1背包模型

// 入参是物品的个数和背包的容量上限，以及物品的重量和价值数组
function knapsack(n, c, w, value) {
    // dp是动态规划的状态保存数组
    const dp = (new Array(c+1)).fill(0)  
    // res 用来记录所有组合方案中的最大值
    let res = -Infinity
    for(let i=1;i<=n;i++) {
        for(let v=c;v>=w[i];v--) {
            // 写出状态转移方程
            dp[v] = Math.max(dp[v], dp[v-w[i]] + value[i])
            // 即时更新最大值
            if(dp[v] > res) {
                res = dp[v]
            }
        }
    }
    return res
}

换硬币

var coinChange = function(coins, amount) {
    let dp = new Array(amount+1).fill(Infinity)
    dp[0] = 0
    for (let coin of coins ) {
      for (let i = 1; i <= amount; i++) {
        if (i - coin >= 0) {
          dp[i] = Math.min(dp[i], dp[i - coin] + 1)
        }
      }
    }
    return dp[amount] === Infinity ? 'Impossible' : dp[amount]
  }

最小路径和

var minPathSum = function (grid) {
    const m = grid.length,
        n = grid[0].length
    for (let i = m - 1; i >= 0; i--) {
        for (let j = n - 1; j >= 0; j--) {
            if (i + 1 < m && j + 1 < n) {
                grid[i][j] += Math.min(grid[i + 1][j], grid[i][j + 1])
            } else if (i + 1 < m) {
                grid[i][j] += grid[i + 1][j]
            } else if (j + 1 < n) {
                grid[i][j] += grid[i][j + 1]
            }
        }
    }
    return grid[0][0]
};

点菜问题

var line;
while(line = readline()){
    line = line.split(" ");
    var count = parseInt(line[0]), //总额度
        nlen = parseInt(line[1]), //菜的数量
        priceArr = [], //菜的价格
        evaArr = []; //菜的评价
    for(let i = 0; i < nlen; i++){
        line = readline().split(" ");
        priceArr.push(parseInt(line[0]));
        evaArr.push(parseInt(line[1]));
    }
    var maxEva = 0,
        prices = new Array(count + 1);
    prices.fill(0);
    for(let i = 0; i < nlen; i++){
        let price = priceArr[i],
            eva = evaArr[i];
        for(let j = count; j >= price; j--){
            prices[j] = Math.max(prices[j], prices[j - price] + eva);
            if(prices[j] > maxEva){
                maxEva = prices[j];
            }
        }
    }
    print(maxEva);
}