# 贪心算法与回溯算法

# 1 贪心算法

# 1 原理

确定问题的最优子结构
设计一个递归算法（对活动选择问题，我们给出了递归式）
证明如果我们做出了一个贪心选择，只剩下一个字问题
证明贪心选择总是安全的
实际一个递归算法实现贪心策略
将递归算法转换为迭代算法

1. 将最优化问题转化为这样的形式， 对其做出一次选择， 只是剩下下一个子问题需要求解
2. 证明做出了贪心选择后，  原问题总存在最优解， 即贪心选择总是安全的
3. 证明做出贪心选择后， 剩余的子问题满足性质： 
其最优解与贪心选择组合即可得到原问题的最优解， 这样就得到了，最优子结构

# 2 快速想法

保证每次操作都是局部最优的，并且最后得到的结果是全局最优的。

# 2 例题

知识的与不同的题型结合

# 1 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，
都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。
如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。
你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

注意：

你可以假设胃口值为正。
一个小朋友最多只能拥有一块饼干。

输入: [1,2,3], [1,1]
输出: 1

解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

证明：假设在某次选择中，贪心策略选择给当前满足度最小的孩子分配第 m 个饼干，第 m 个饼干为可以满足该孩子的最小饼干。假设存在一种最优策略，给该孩子分配第 n 个饼干，并且 m < n。我们可以发现，经过这一轮分配，贪心策略分配后剩下的饼干一定有一个比最优策略来得大。因此在后续的分配中，贪心策略一定能满足更多的孩子。也就是说不存在比贪心策略更优的策略，即贪心策略就是最优策略。

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int gi = 0, si = 0;
        
        while(gi < g.length && si < s.length ){
            if(g[gi] <= s[si]){
                gi++;
            }
            si++;
        }
        
        return gi;
    }
}

# 2 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]

输出: 5

解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。

注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

记录遍历过的数组的最小值，每个元素减去最小值与ans比较

public int maxProfit(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += (prices[i] - prices[i - 1]);
        }
    }
    return profit;
}

# 3 买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4]

输出: 7

解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。

随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

遍历数组，找出连续的vally peak,相加差值。

class Solution {
    public int maxProfit(int[] prices) {
        int i = 0;
        int valley = 0;
        int peak = 0;
        int maxprofit = 0;
        while (i < prices.length - 1) {
            while (i < prices.length - 1 && prices[i] >= prices[i + 1])
                i++;
            valley = prices[i];
            while (i < prices.length - 1 && prices[i] <= prices[i + 1])
                i++;
            peak = prices[i];
            maxprofit += peak - valley;
        }
        return maxprofit;
    }
}

遍历数组，每次都是最优解，找到每次后一个比前一个大的一对数据

class Solution {
    public int maxProfit(int[] prices) {
       int len = prices.length;
        
        int sum =0;
        for(int  i = 1; i<len;  i++){
            if(prices[i-1] < prices[i]){
                sum += prices[i] -prices[i-1] ;
            }
        }
        return sum;
    }
}

# 4 加油站

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。

示例 1:

输入:

gas = [1,2,3,4,5]

cost = [3,4,5,1,2]

输出: 3

class Solution {
  public int canCompleteCircuit(int[] gas, int[] cost) {
    int n = gas.length;

    int total_tank = 0;
    int curr_tank = 0;
    int starting_station = 0;
    for (int i = 0; i < n; ++i) {
      total_tank += gas[i] - cost[i];
      curr_tank += gas[i] - cost[i];
      // If one couldn't get here,
      if (curr_tank < 0) {
        // Pick up the next station as the starting one.
        starting_station = i + 1;
        // Start with an empty tank.
        curr_tank = 0;
      }
    }
    return total_tank >= 0 ? starting_station : -1;
  }
}

# 2 回溯算法

# 1 定义

#

# 1 精确定义

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就 “回溯” 返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为 “回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
-回溯法的算法本质是：n 叉树的遍历

# 2 另一种视角

回溯法是一种系统搜索问题解空间的方法。为了实现回溯，需要给问题定义一个解空间。
说到底它是一种搜索算法。只是这里的搜索是在一个叫做解空间的地方搜索。
而往往所谓的dfs，bfs都是在图或者树这种数据结构上的搜索。
根据定义来看，要实现回溯，需要两点   1搜索， 2解空间


先看什么是解空间。
就是形如数组的一个向量[a1,a2,....,an]。这个向量的每个元素都是问题的部分解，
只有当这个数组的每一个元素都填满(得到全部解)的时候，才表明这个问题得到了解答。

再看搜索。
最简单的就是for循环，上面的向量有n个维度，因此就是n个for循环。

形如：
for(求a1位置上的解)
   for(求a2位置上的解)
      for(求a3位置上的解)
       ......
       ......
       for(求an位置上的解)
但是如果n是100？n是100000？那么如何回溯？

# 3 模板

void backtrack(int i,int n,other parameters){
  if( i == n){
    //get one answer
    record answer;
    return;
  }
//下面的意思是求解空间第i个位置上的下一个解
for(next ans in position i of solution space){
    backtrack(i+1,n,other parameters);
    }
}

# 2 用回溯法解题的一般步骤：

针对所给问题，确定问题的解空间：首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。
确定结点的扩展搜索规则
以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

# 3 回溯法的一般实现：

回溯法一般有两种代码实现方案，递归方法和非递归方法。

# 4 回溯法结果

找到一个可能存在的正确的答案
在尝试了所有可能的分步方法后宣告该问题没有答案

# 4 实例

数组中的子集，组合，排列，
树中所有路径，所有节点的结果，
排列，组合问题。

# ·1 组合

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

class Solution {
   public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> combinations = new ArrayList<>();
    List<Integer> combineList = new ArrayList<>();
    backtracking(combineList, combinations, 1, k, n);
    return combinations;
}

private void backtracking(List<Integer> combineList, List<List<Integer>> combinations, int start, int k, final int n) {
    if (k == 0) {
        combinations.add(new ArrayList<>(combineList));
        return;
    }
    for (int i = start; i <= n - k + 1; i++) {  // 剪枝
        combineList.add(i);
        backtracking(combineList, combinations, i + 1, k - 1, n);
        combineList.remove(combineList.size() - 1);
    }
}
}

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Solution {

    private List<List<Integer>> res = new ArrayList<>();

    private void findCombinations(int n, int k, int begin, Stack<Integer> pre) {
        if (pre.size() == k) {
            // 够数了，就添加到结果集中
            res.add(new ArrayList<>(pre));
            return;
        }
        // 关键在于分析出 i 的上界
        for (int i = begin; i <= n; i++) {
            pre.add(i);
            findCombinations(n, k, i + 1, pre);
            pre.pop();
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        // 特判
        if (n <= 0 || k <= 0 || n < k) {
            return res;
        }
        // 从 1 开始是题目的设定
        findCombinations(n, k, 1, new Stack<>());
        return res;
    }
}

← 数学动态规划 →