数据结构三大算法（案例解析）
作者：championsky | 发布时间：
图文讲解
概述
本文讲述数据结构中最常用到的三大算法：分治法、动态规划法和贪心算法，主要从这些算法的经典案例入手来对算法进行分析和理解。
分治法
分治法可以通俗的理解为将一条大鱼分成好几块，分别料理每一块鱼肉，然后再组成一道菜。也就是说分治法是将一个大的问题分成好多个小的问题，这些小问题解决后从而解决整个大问题，在处理过程中这些小问题的处理方法可以不尽相同。我们从下面这个案例来进行进一步的分析和理解。
问题描述
设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。
算法思路与设计
把问题简化为在n个元素的集合中找最大最小值，将这n个数分为两组，分别找出最大值和最小值。然后递归分解直到每组的个数小于等于2。利用二分搜索的思想，在数组中查找关键字x，low和top为数组头尾下标。当low<=top时，如果x等于数组中间值，则表示x在数组中，返回下标i，j；如果x大于数组中间值，则low等于中间值+1，如果x小于中间值，则top等于中间值+1，经过不断循环，直到low大于top；如果还是没找到x，则把top复制给i，low赋值给j，然后返回下标i，j。完整代码如下。
C语言实现
#include<stdio.h>
int search(int a[],int length, int x)
{
int i = 0, j = 0;
int s= -1;
int top = length - 1;
int mid = 0;
int low = 0;
while (low <= top)
{
mid = (low + top) / 2;
if (a[mid] == x)
{
s = mid;
}
if (a[mid] < x)
{
low = mid + 1;
}
else
{
top = mid - 1;
}
}
if (s == -1)
{
i = top;
j = low;
}
else
{
i = s;
j = i;
}
printf("%d %d",i,j);
return 0;
}
int main()
{
int arr[100];
int x,n;
scanf("%d %d",&n,&x);
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
search(arr,n,x);
return 0;
}JAVA语言实现
public class BinarySearch {
private static int[] array = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
private static int low = 0;
private static int high = array.length - 1;
private static int[] binarySearch(int[] array, int low, int high, int target) {
int i = -1; // 小于x的最大元素位置
int j = -1; // 大于x的最小元素位置
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] == target) {
i = mid;
j = mid;
break;
} else if (array[mid] < target) {
i = mid;
low = mid + 1;
} else {
j = mid;
high = mid - 1;
}
}
return new int[]{i, j};
}
public static void main(String[] args) {
int target = 8;
int[] result = binarySearch(array, low, high, target);
System.out.println("小于" + target + "的最大元素位置为：" + result[0] + "，大于" + target + "的最小元素位置为：" + result[1]);
}
}Python语言实现
def binary_search(array, low, high, target):
i = -1 # 小于x的最大元素位置
j = -1 # 大于x的最小元素位置
while low <= high:
mid = low + (high - low) // 2
if array[mid] == target:
i = mid
j = mid
break
elif array[mid] < target:
i = mid
low = mid + 1
else:
j = mid
high = mid - 1
return i, j
if __name__ == '__main__':
array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
low = 0
high = len(array) - 1
target = 8
result = binary_search(array, low, high, target)
print("小于{}的最大元素位置为：{}，大于{}的最小元素位置为：{}".format(target, result[0], target, result[1]))动态规划法
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。
问题描述
给定n(n<=100)种物品和一个背包。物品i的重量是wi，价值为vi，背包的容量为C(C<=1000)。问:应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品i装入多次，也不能只装入部分物品i。
算法思路与设计
动态规划就是一个填表的过程。现在有1个背包，背包容量是10，有5个物品，编号为1，2，3，4，5，他们都有各自的重量和价格。要求在不超过背包容量的情况下，使背包装载物品的价值最大。我们可以吧问题拆分为五个子问题。 我们可以将1，2，3，4，5子问题的答案都存入一张表中。因为求解2子问题，需要用到1子问题的答案(2的每一步方案要与1的每一步方案比较，如何2的该步方案优于1所对应的方案。则将2的这步方案标为可行。如果不优于1的，或者不满足问题的约束条件，则舍弃该方案。继续沿用该步所对应的1的方案作为该步的方案)。求解3子问题，需要用到2子问题的答案，一直递推到求解5子问题，需要用到4子问题的答案。而5子问题就是原问题。5子问题的答案就是最终原问题的解。完整代码如下：
C语言实现
#define EMPTY
#include<stdio.h>
#include <iostream>
using namespace std ;
int main()
{
int V ,T;
scanf("%d %d",&T,&V);
int f[V+1],w[100],c[100];
for(int m=0;m<T;m++){
scanf("%d",&c[m]);
scanf("%d",&w[m]);
}
const int INF = -66536 ;
#ifdef EMPTY
for(int i = 0 ; i <= V ;i++)
f[i] = 0 ;
#else
f[0] = 0 ;
for(int i = 1 ; i <= V ;i++)
f[i] = INF ;
#endif
for(int i = 0 ; i < T ; i++)
{
for(int v = V ; v >= c[i] ;v--)
{
f[v] = max(f[v-c[i]] + w[i] , f[v]);
}
}
cout<<f[V];
return 0;
}
Java语言实现
public class Knapsack {
private static int[] weights = {5, 3, 2, 1, 4}; // 物品的重量
private static int[] values = {10, 8, 7, 4, 6}; // 物品的价值
private static int n = weights.length;
private static int C = 10; // 背包的容量
private static int[][] dp = new int[n+1][C+1]; // 动态规划数组
private static void knapsack() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= C; j++) {
if (j < weights[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]);
}
}
}
}
public static void main(String[] args) {
knapsack();
System.out.println("背包最大价值为：" + dp[n][C]);
}
}
Python语言实现
def knapsack(weights, values, C):
n = len(weights)
dp = [[0] * (C+1) for _ in range(n+1)] # 初始化动态规划数组
for i in range(1, n+1):
for j in range(1, C+1):
if j < weights[i-1]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
return dp[n][C]
if __name__ == '__main__':
weights = [5, 3, 2, 1, 4]
values = [10, 8, 7, 4, 6]
C = 10
max_value = knapsack(weights, values, C)
print("背包最大价值为：{}".format(max_value))贪心算法
贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。
问题描述
有n头牛（1<=n<=50,000)要挤奶。给定每头牛挤奶的时间区间A,B。牛需要呆在畜栏里才能挤奶。一个畜栏同一时间只能容纳一头牛。问至少需要多少个畜栏，才能完成全部挤奶工作。（在同一个畜栏的两头牛，它们挤奶时间区间不能在端点重合）
算法思路与设计
我们可以把每头牛的挤奶时间按开始时间递增或者按结束时间递赠排序，求出一个最大的能兼容这些时间区间的子集，从而把这些牛安排早一个畜栏中；如果还有未安排完的奶牛，即将其时间集合再求其最大的子集，再把它们安排在这第二个畜栏中。如此一直排到安排完为止，而这些子集的个数也就是畜栏的最小个数。完整代码如下：
C语言实现
#include <stdio.h>
#include <stdlib.h>
// 定义牛的结构体，包括挤奶开始时间和结束时间
typedef struct {
int start_time;
int end_time;
} Cow;
// 比较函数，按挤奶结束时间升序排列
int cmp(const void *a, const void *b) {
Cow *c1 = (Cow *)a;
Cow *c2 = (Cow *)b;
return c1->end_time - c2->end_time;
}
int min_stalls(Cow *cows, int n) {
// 按挤奶结束时间升序排列
qsort(cows, n, sizeof(Cow), cmp);
int count = 1; // 至少需要一个畜栏
int end_time = cows[0].end_time; // 初始结束时间为第一头牛的挤奶结束时间
for (int i = 1; i < n; i++) {
if (cows[i].start_time >= end_time) {
// 如果下一头牛的挤奶开始时间在当前畜栏结束时间之后，可以将其放在同一个畜栏中
end_time = cows[i].end_time;
} else {
// 否则，需要分配新的畜栏
count++;
}
}
return count;
}
int main() {
int n = 5;
Cow cows[] = { {1, 3}, {2, 5}, {3, 7}, {5, 8}, {7, 10} };
int min_num_stalls = min_stalls(cows, n);
printf("至少需要%d个畜栏\n", min_num_stalls);
return 0;
}在这个算法中，我们首先定义了一个牛的结构体，包括挤奶开始时间和结束时间。然后，我们定义了一个比较函数，按挤奶结束时间升序排列，以用于sort函数排序。接下来，我们实现了一个名为min_stalls的函数，该函数使用贪心算法来计算至少需要多少个畜栏。
算法的主要思路是：将所有牛按照挤奶结束时间升序排列，从前往后依次遍历每头牛。对于每头牛，如果其挤奶开始时间在当前畜栏的结束时间之后，说明可以将其放在同一个畜栏中，直接更新当前畜栏的结束时间。否则，需要分配新的畜栏。遍历结束后，记录分配的畜栏数量即为所求。
最后，在主函数中，我们定义了一个5头牛的数组，调用min_stalls函数来计算所需的最小畜栏数，并将结果打印输出。
Java语言实现
import java.util.Arrays;
class Cow implements Comparable<Cow> {
private int start_time;
private int end_time;
public Cow(int start_time, int end_time) {
this.start_time = start_time;
this.end_time = end_time;
}
public int getStartTime() {
return start_time;
}
public int getEndTime() {
return end_time;
}
public int compareTo(Cow another) {
return this.end_time - another.end_time;
}
}
public class Main {
public static int min_stalls(Cow[] cows) {
Arrays.sort(cows); // 按挤奶结束时间从小到大排序
int count = 1; // 至少需要一个畜栏
int end_time = cows[0].getEndTime(); // 初始结束时间为第一头牛的挤奶结束时间
for (int i = 1; i < cows.length; i++) {
if (cows[i].getStartTime() >= end_time) {
// 如果下一头牛的挤奶开始时间在当前畜栏结束时间之后，可以将其放在同一个畜栏中
end_time = cows[i].getEndTime();
} else {
// 否则，需要分配新的畜栏
count++;
}
}
return count;
}
public static void main(String[] args) {
Cow[] cows = { new Cow(1, 3), new Cow(2, 5), new Cow(3, 7), new Cow(5, 8), new Cow(7, 10) };
int min_num_stalls = min_stalls(cows);
System.out.println("至少需要" + min_num_stalls + "个畜栏");
}
}在这个Java实现中，我们同样定义了一个Cow类来表示每头牛。Cow类中包含挤奶开始时间和结束时间两个私有属性，以及构造函数和获取属性值的方法。我们还实现了Comparable接口，按挤奶结束时间从小到大排序。
与C语言实现类似，我们在min_stalls函数中使用贪心算法来计算至少需要多少个畜栏。算法的主要思路与C语言实现相同。
在主函数中，我们定义一个Cow类型的数组，并调用min_stalls方法来计算所需的最小畜栏数，并将结果打印输出。
Python语言实现
class Cow:
def __init__(self, start_time, end_time):
self.start_time = start_time
self.end_time = end_time
def get_start_time(self):
return self.start_time
def get_end_time(self):
return self.end_time
def __lt__(self, other):
return self.end_time < other.end_time
def min_stalls(cows):
cows.sort() # 按挤奶结束时间从小到大排序
count = 1 # 至少需要一个畜栏
end_time = cows[0].get_end_time() # 初始结束时间为第一头牛的挤奶结束时间
for i in range(1, len(cows)):
if cows[i].get_start_time() >= end_time:
# 如果下一头牛的挤奶开始时间在当前畜栏结束时间之后，可以将其放在同一个畜栏中
end_time = cows[i].get_end_time()
else:
# 否则，需要分配新的畜栏
count += 1
return count
if __name__ == "__main__":
cows = [Cow(1, 3), Cow(2, 5), Cow(3, 7), Cow(5, 8), Cow(7, 10)]
min_num_stalls = min_stalls(cows)
print("至少需要%d个畜栏" % min_num_stalls)在Python实现中，我们同样定义了一个Cow类来表示每头牛。Cow类中包含挤奶开始时间和结束时间两个属性，以及初始化方法和获取属性值的方法。我们还实现了__lt__方法，用于指定按挤奶结束时间从小到大排序。
与前两个实现类似，我们在min_stalls函数中使用贪心算法来计算需要多少个畜栏。算法的主要思路与前两个实现类似。
在主函数中，我们定义一个Cow类型的列表，并调用min_stalls函数来计算所需的最小畜栏数，并将结果打印输出。