GREEDY ALGORITHM

2019-08-01 本文已影响0人世界上的一道风

贪心算法原理

贪心算法以动态规划方法为基础，区别于贪心算法在每一次做出贪心选择后，子问题之一为空，下一步只需继续分解非空子问题。
贪心算法的两个关键要素：

贪心选择性质：可以通过做出局部最优选择来构造全局最优选择。这也是与动态规划不同的地方，动态规划中每一个步骤都要进行选择，选择依赖于子问题的解。贪心算法总是选择当前最佳的选择，然后求解剩下的唯一的子问题。因此，贪心算法通常是自顶向下的，进行一次又一次选择，将给定的问题实例变得更小。

最优子结构：最优子结构的定义是，一个问题的最优解包含了其子问题的最优解。这个性质也是能否运用贪心算法和动态规划的关键。因此一个问题是否能应用贪心算法，需要论证每个步骤的贪心选择是否会生成原问题的最优解。（数学归纳）

数学归纳

undo

具体问题

1. 活动选择问题

问题描述：使用同一资源的 $n$ 个任务的集合 $S={(a_1,....,a_n)}$ ，因为该资源每次只能被一个任务使用，给出每个任务 $a_i$ 使用资源的开始及结束时间，要求找出使用该资源的最大任务子集（尽可能多的任务被使用），又因为任务不重叠，因此称这些集合（解不止一个，贪心算法给出一个）是最大兼容任务子集。

其中开始时间 $s_i$ ，结束时间为 $f_i$ ，具体实例如：

image.png

这个例子里有两个最大兼容任务活动子集， ${(a_1,a_4,a_8,a_{11})}$ 还有 ${(a_2,a_4,a_9,a_{11})}$ 的数目最多且元素不重叠。
为了后面应用贪心算法，先按结束时间对 $f_i$ 做了排序。

先照书上说的用DP先分析：
设 $S_{i,j}$ 表示在 $a_i$ 结束之后， $a_j$ 开始之前的活动集合。在 $S_{i,j}$ 中需求一个最大兼容任务活动子集 $A_{i,j}$ 。假设这个最优解 $A_{i,j}$ 包含有任务 $a_k$ ,按照DP的思想便可以用子问题定义原问题，有：
（1） $A_{i,k}=A_{i,j}\bigwedge S_{i,j}$ 和 $A_{k,j}=A_{i,j}\bigwedge S_{k,j}$ ；
（2） $A_{i,j}=A_{i,k}\bigvee\{a_k\} \bigvee A_{k,j}$ 。

因此 $S_{i,j}$ 中最大兼容任务活动子集 $A_{i,j}$ 的个数为：（3） $|A_{i,k}| + |A_{k,j}| + 1$ 。

在式子（2）里我们假设了 $A_{i,j}$ 里包含了两个子问题 $S_{i,k}$ 和 $S_{k,j}$ 的最优解。可以用书上说的验证方法，设 $S_{k,j}$ 的一个兼容活动子集为 $\hat A_{k,j}$ ,其大小满足 $|\hat A_{k,j}| \ge | A_{k,j}|$ ,将 $\hat A_{k,j}$ 作为 $S_{i,j}$ 的最优解一部分，构造出一个兼容活动子集，其大小大于（3）,这与 $A_{i,j}$ 为最优解矛盾，因此，证明 $A_{i,j}$ 里包含了两个子问题 $S_{i,k}$ 和 $S_{k,j}$ 的最优解。

形式化公式（3），用 $c_{i,j}$ 表示集合 $S_{i,j}$ 的最优解大小，可得递归式：
$c_{i,j} = c_{i,k} + c_{k,j} +1$

上面假设最优解包含了 $a_k$ ，实际并不知道，需要寻找 $k$ ：
$c_{i,j} = 0 , \ if ： S_{i,j} = \emptyset\\ c_{i,j} = \max_{a_{k} \in S_{i,j}}{(c_{i,k} + c_{k,j} +1)}, \ if ： S_{i,j} \neq\emptyset$

c++代码：

#include <iostream>
#include<vector>
#include<climits>
using namespace std;

int DP_Activity(const vector<int> &start, const vector<int> &end)
{
  const int n = start.size();
  vector<vector<int>> table(n, vector<int>(n, 0));
  vector<int> path;
  //第一个位置为虚拟活动a_0
  for(int i=0; i<n; ++i)
  {
    for (int j=i+1; j<n; ++j)
    {
      for (int k=i+1;k<j;++k)
      {  
        if(start[k]>end[i] && end[k] < start[j])
        {
          int tmp = table[i][k] + table[k][j] + 1;
          if (tmp > table[i][j])
          {
            table[i][j] = tmp;
            path.push_back(k);
          }
        }
      } 
    }
  }
  for (int i=0; i<table.size(); ++i)
  {
    for(int j=0; j<table.size(); ++j)
    {
      cout << table[i][j] << " ";
    }
  cout<< endl;
  }
  return table[0][n-1];
}
int main() {
  //第一个位置和最后一个位置是虚拟位
  vector<int> s={0,1,3,0,5,3,5,6,8,8,2,12,INT_MAX};
  vector<int> f={0,4,5,6,7,9,9,10,11,12,14,16, INT_MAX};
  int ans = DP_Activity(s,f);
  cout << "Answer is : "<< ans << endl;
}


 ./main
0 0 0 0 1 0 1 1 2 2 0 3 4
0 0 0 0 0 0 0 0 1 1 0 2 3
0 0 0 0 0 0 0 0 0 0 0 1 2
0 0 0 0 0 0 0 0 0 0 0 1 2
0 0 0 0 0 0 0 0 0 0 0 1 2
0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
Answer is : 4

参考下别人的，多个角度看一个问题收获更多：https://www.cnblogs.com/hapjin/p/5573419.html

贪心算法

先确定所做的贪心选择方法：直觉上，先选最早结束的活动，那就可以剩下更多的资源供其他活动选择，即选择某一最早结束的活动 $a_k$ 之后，剩下的问题规模变小了，活动集合为 $S_k=\{s_i \ge f_k\}$ 。

书上证明了这样一种思路可以得到最优解。主要思路是 $a_m$ 是 $S_k$ 中最早结束的活动，假设有 $a_j$ 是 $A_k$ 的最早结束活动，替换 $a_j$ 和 $a_k$ ，得到结论 $a_k$ 也是属于一个最大兼容活动集合。

c++代码，运行时间为 $\Theta(n)$ ：

#include <iostream>
#include<vector>
#include<climits>
using namespace std;

void Greedy_Recursive_Activity(const vector<int> &start, const vector<int> &end, const int k, const int n, vector<int> &ans)
/*
Params: 
  start: 活动开始时间
  end: 活动结束时间（已经升序排列）
  k: S活动集合区间的左边界
  n:S活动集合区间的右边界
Return:
  void: 使用ans返回S[k,n]内的最大的兼容区间大小
*/
{
  int m=k+1;
  while(m<=n && start[m]<end[k]) //找到最早结束的活动
  {
    m += 1;
  }
  if(m<=n)
  {
    ans.push_back(m);
    Greedy_Recursive_Activity(start,end,m,n,ans);
  }
  else
    return;
}
int main() {
  //第一个位置和最后一个位置是虚拟位
  vector<int> s={0,1,3,0,5,3,5,6,8,8,2,12,INT_MAX};
  vector<int> f={0,4,5,6,7,9,9,10,11,12,14,16, INT_MAX};
  vector<int> ans;
  int n = s.size();
  Greedy_Recursive_Activity(s,f,0,n-2,ans);
  for (auto i:ans)
    cout << i << " ";
  
  cout << endl << "Answer is : "<< ans.size() << endl;
}

1 4 8 11
Answer is : 4

迭代版本：

#include <iostream>
#include<vector>
#include<climits>
using namespace std;

vector<int> Greedy_Iter_Activity(const vector<int> &start, const vector<int> &end)
/*
Params: 
  start: 活动开始时间
  end: 活动结束时间（已经升序排列）
Return:
  vector<int>: 使用ans返回S[k,n]内的最大的兼容区间大小
*/
{
  vector<int> ans;
  int n = start.size();
  ans.push_back(1);
  int k=1;
  for (int m=2; m<n-1; ++m)
  {
    if(start[m] > end[k])
    {

      ans.push_back(m);
      k = m;
    }
  }
  return ans;
}
int main() {
  //第一个位置和最后一个位置是虚拟位
  vector<int> s={0,1,3,0,5,3,5,6,8,8,2,12,INT_MAX};
  vector<int> f={0,4,5,6,7,9,9,10,11,12,14,16, INT_MAX};
  vector<int> ans;
  int n = s.size();
  ans = Greedy_Iter_Activity(s,f);
  for (auto i:ans)
    cout << i << " ";
  
  cout << endl << "Answer is : "<< ans.size() << endl;
}

背包问题9讲学习记录

1. 01背包

定义：给定 $N$ 个物品，没种物品都有自己的重量 $w_i$ 和价值 $v_i$ ，在限定容量为 $C$ 内，选择若干个物品（每种物品可以选0个或者1个），设计选择方案使得物品的总价值最高。
0-1背包问题的定性：贪婪算法无法得到最优解。（参见算法导论）
0-1背包问题的递推关系
设问题为取前 $i$ 个物品，放入容量为 $W$ 的背包，获得的总价值为 $F(i,W)$ ,由取不取第 $i$ 个物品，可以用子问题定义原问题：
$F(i, W)= \begin{cases} 0, & \ if： i = 0 \\ 0, & \ if: W = 0 \\ F(i-1,W), & \ if: w_i > W \\ \max\{F(i-1,W), v_i + F(i-1, W-w_i)\}, & \ otherwise \end{cases}$

最优解回溯
- $V(i,j)=V(i-1,j)$ 时，说明没有选择第 $i$ 个商品，则回到 $V(i-1,j)$ ；
- $V(i,j)=V(i-1,j-w(i))+v(i)$ 时，说明装了第 $i$ 个商品，该商品是最优解组成的一部分，随后我们得回到装该商品之前，即回到 $V(i-1,j-w(i))$ ；
- 一直遍历到 $i＝0$ 结束为止，所有解的组成都会找到。

例子：

image.png

c++代码：

#include <iostream>
#include<vector>
#include<climits>
using namespace std;

void Zero_One_knapsack(const vector<int> &weight, const vector<int> &value, const int capacity, vector<vector<int>> &ans, vector<vector<int>> &path)
/*
Params:
  weight: weight list of objects.
  value: corresponding valus of each object.
  capacity: total size of knapsack.
  ans: return answer table.
  path: return backtracking table.
Return:
  None.
*/
{
  const int n = weight.size();
  vector< vector<int>> _ans(n, vector<int>(capacity+1, 0));
  vector< vector<int>> _path(n, vector<int>(capacity+1, 0));
  for(int i=1; i<n;++i)
  {
    for(int j=1; j<=capacity; ++j)
    {
      if(j < weight[i])  // whether backpack size enough for weight
      {
        _ans[i][j] = _ans[i-1][j]; 
      }else{
        if (_ans[i-1][j] > _ans[i-1][j-weight[i]] + value[i])
        {
          _ans[i][j] = _ans[i-1][j];
        }
        else{
          _ans[i][j] = _ans[i-1][j-weight[i]] + value[i];
          _path[i][j] = i;
        }
      }
    }
  }

  ans = _ans;
  path = _path; 
}

void Backtracking(const vector<vector<int>> &ans, const vector<int> &weight, const vector<int> &value, const int i, const int j)
/*
Params:
  weight: weight list of objects.
  value: corresponding valus of each object.
  capacity: total size of knapsack.
  i: size of objects (without zero visual item).
  j: size of backpack.
Return:
  None.
*/
{
  if (i > 0)
  {
    if (ans[i][j] == ans[i-1][j])
    {
      Backtracking(ans, weight, value, i-1, j);
    }
    else
    {
      if (j-weight[i]>=0 && ans[i][j] == ans[i-1][j-weight[i]] + value[i])
      {
        cout<< i << " ";
        Backtracking(ans, weight, value, i-1, j-weight[i]);
      }

    }
  }
}

int main() {
  int mark = 0;
  vector<int> weight={mark,1,2,5,6,7};
  vector<int> value={mark,1,6,18,22,28};
  const int capacity = 11;
  vector<vector<int>> ans;
  vector<vector<int>> path;
  Zero_One_knapsack(weight, value, capacity, ans, path);

  for (int i=0; i< ans.size(); ++i)
  {
    for(int j=0; j < ans[0].size(); ++j)
        cout << ans[i][j] << " ";
    cout << endl;
  }  
  cout << endl << "Answer is : "<< ans[ans.size()-1][capacity] << endl;
  Backtracking(ans,weight, value, 5, 11);
}

0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1 1
0 1 6 7 7 7 7 7 7 7 7 7
0 1 6 7 7 18 19 24 25 25 25 25
0 1 6 7 7 18 22 24 28 29 29 40
0 1 6 7 7 18 22 28 29 34 35 40

Answer is : 40
4 3

reference:
1. 0-1背包问题的定性
2. 背包问题最优解回溯
3. 《背包⑨讲》