配套作业——贪心策略

需求

• 贪心策略解决背包问题或者活动安排问题（二选一），编程实现

• dijkstra算法编程实现 或者Prim算法编程实现（二选其一）

• Kruskal算法编程实现

• Huffman编码编程实现（选做）

实现

背包问题

• 代码实现
• 测试运行

#include<iostream>

const int N = 10000;

using namespace std;
double maxWeight;		//最大承受重量
double currentWeight;	//临时重量
double bestValue;		//最大价值
int n;					//物品数量
double value[N];		//记录物品价值价值的数组
double weight[N];		//记录每个物品重量的数组
double vw[N];			//记录单位利益值的数组
double x[N];			//记录解向量的数组

//利用单位利益值对物品的质量和价值数组进行排序
void sort_vw(int low, int high) {
	if (low >= high) return;
	int l = low, h = high, x = vw[low];
	while (low < high) {
		//这里快排注意一下，我们要从大到小排列
		while ((low < high) && (vw[high] <= x)) high--;
		swap(vw[low], vw[high]);
		swap(weight[low], weight[high]);
		swap(value[low], value[high]);
		while ((low < high) && (vw[low] >= x)) low++;
		swap(vw[low], vw[high]);
		swap(weight[low], weight[high]);
		swap(value[low], value[high]);
	}
	sort_vw(l, high - 1);
	sort_vw(high + 1, h);

}



void greedy() {

	//对物品的进行排序
	sort_vw(0, n - 1);

	for (int i = 0; i < n; i++) x[i]=0;
	currentWeight = maxWeight;

	int i = 0;
	for ( i = 0; i < n; i++) {
		//加入物体重量大于剩余重量 结束循环
		if (weight[i] > currentWeight) break;
		//可以加入则加入完整物品
		x[i] = 1;
		currentWeight -= weight[i];//更新剩余质量
		bestValue += value[i];//更新最大价值

	}
	//物品太大，加不进去的情况，切割后加进去
	if (i < n) {
		x[i] = currentWeight / weight[i];
		bestValue = x[i] * value[i];
	}
}



int main() {
	cout << "请输入背包最大承受重量和物品数量n" << endl;
	cin >> maxWeight >> n;
	cout << "请输入n个物品的重量和价值" << endl;
	for (int i = 0; i < n; i++) { 
		cin >> weight[i] >> value[i]; 
		//处理单位利益值的数组
		vw[i] = value[i] / weight[i];
	}

	greedy();


	cout << "\n排序后的物品顺序" << endl;
	for (int i = 0; i < n; i++) { 
		cout <<weight[i] <<"  "<<value[i]<<endl;

	}

	cout << "\n最大价值为" << bestValue << endl;
	cout << "加人背包的物品情形" << endl;
	for (int i = 0; i < n; i++) {
		cout << " " << x[i];
	}



	return 0;
}

dijkstra算法

• 代码实现
• 测试运行

• dijkstra在无权图上实际上就是bfs，比如我们在迷宫问题上使用的bfs算法也就是dijstra算法

• 但是dijkstra算法可以求有权图的最短单源路径，但是bfs算法不可以

• 这里代码直接沿用这篇文章Dijkstra算法详解 通俗易懂 - 知乎 (zhihu.com)

  

  public class Dijkstra {
      public static int[] dijkstra(int[][] graph,int startVertex){
          //初始化 以求出最短路径的点 result[]
          int length = graph.length;
          int[] result = new int[length];
          for (int i = 0; i < length; i++) {
              result[i] = -1;
          }
          result[startVertex] = 0 ;
          // 初始化 未求出最短路径的点 notFound[]
          int[] notFound = new int[length];
          for (int i = 0; i < length; i++) {
              notFound[i] = graph[startVertex][i];
          }
          notFound[startVertex] = -1;
          // 开始 Dijkstra 算法
          for (int i = 1; i < length; i++) {
              //1. 从「未求出最短路径的点」notFound 中取出 最短路径的点
              //1.1 找到最短距离的点
              int min = Integer.MAX_VALUE;
              int minIndex = 0;
              for (int j = 0; j < length; j++) {
                  if (notFound[j] > 0 && notFound[j] < min){
                      min = notFound[j];
                      minIndex = j;
                  }
              }
              //1.2 将最短距离的点 取出 放入结果中
              result[minIndex] = min;
              notFound[minIndex] = -1;
              //2. 刷新 「未求出最短距离的点」 notFound[] 中的距离
              //2.1 遍历刚刚找到最短距离的点 (B) 的出度 (BA、BB、BC、BD)
              for (int j = 0; j < length; j++) {
                  // 出度可通行(例如 BD:graph[1][3]  > 0)
                  // 出度点不能已经在结果集 result中(例如 D: result[3] == -1)
                  if (graph[minIndex][j] > 0
                          && result[j] == -1){
                      int newDistance = result[minIndex] + graph[minIndex][j];
                      //通过 B 为桥梁，刷新距离
                      //（比如`AD = 6 < AB + BD = 4` 就刷新距离）（ -1 代表无限大）
                      if (newDistance < notFound[j] || notFound[j]==-1){
                          notFound[j] = newDistance;
                      }
                  }
              }
  
          }
          return result;
      }
      /** 测试案例 */
      public static void main(String[] args) {
          char[] vertices = new char[]{'A','B','C','D'};
          int[][] graph = new int[][]{
                  {0, 2, -1, 6}
                  , {2, 0, 3, 2}
                  , {-1, 3, 0, 2}
                  , {6, 2, 2, 0}};
          int[] dijkstra = dijkstra(graph, 0);
  
  
          System.out.println("A到各点最短路径");
          for (char temp: vertices){
              System.out.print(temp+" ");
          }
          System.out.println();
          for (int i : dijkstra) {
              System.out.print(i+" ");
          }
      }
  }

Kruskal(克鲁斯卡尔)算法

• 代码实现
• 测试运行

• 参考了文章kruskal算法（克鲁斯卡尔算法）详解 (biancheng.net)

• 这里我们判断是否形成回路的方法：初始状态下，为连通网中的各个顶点配置不同的标记。对于一个新边，如果它两端顶点的标记不同，就不会构成环路，可以组成最小生成树。

• 在下面示例代码中 A B C D T S分别用 1 2 3 4 5来标记

import java.util.Arrays;
import java.util.Scanner;

public class Kruskal {
    static int N = 9; // 图中边的数量
    static int P = 6; // 图中顶点的数量
    //构建表示路径的类
    public static class edge implements Comparable<edge>{
        //每个路径都有 2 个顶点和 1 个权值
        int initial;
        int end;
        int weight;
        public edge(int initial, int end, int weight) {
            this.initial = initial;
            this.end = end;
            this.weight = weight;
        }
        //对每个 edge 对象根据权值做升序排序
        @Override
        public int compareTo(edge o) {
            return this.weight - o.weight;
        }
    }

    public static void kruskal_MinTree(edge[] edges,edge [] minTree) {
        int []assists = new int[P];
        //每个顶点配置一个不同的标记值
        for (int i = 0; i < P; i++) {
            assists[i] = i;
        }
        //根据权值，对所有边进行升序排序
        Arrays.sort(edges);
        //遍历所有的边
        int num = 0;
        for (int i = 0; i < N; i++) {
            //找到当前边的两个顶点在 assists 数组中的位置下标
            int initial = edges[i].initial - 1;
            int end = edges[i].end - 1;
            //如果顶点位置存在且顶点的标记不同，说明不在一个集合中，不会产生回路
            if (assists[initial] != assists[end]) {
                //记录该边，作为最小生成树的组成部分
                minTree[num] = edges[i];
                //计数+1
                num++;
                int elem = assists[end];
                //将新加入生成树的顶点标记全不更改为一样的
                for (int k = 0; k < P; k++) {
                    if (assists[k] == elem) {
                        assists[k] = assists[initial];
                    }
                }
                //如果选择的边的数量和顶点数相差1，证明最小生成树已经形成，退出循环
                if (num == P - 1) {
                    break;
                }
            }
        }
    }
    
    public static void display(edge [] minTree) {
        System.out.println("最小生成树为：");
        int cost = 0;
        for (int i = 0; i < P - 1; i++) {
            System.out.println(minTree[i].initial+" - "+ minTree[i].end+" 权值为："+minTree[i].weight);
            cost += minTree[i].weight;
        }
        System.out.print("总权值为:"+cost);
    }

    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        edge[] edges = new edge[N];
        edge[] minTree = new edge[P-1];
        System.out.println("请输入图中各个边的信息：");
        for(int i=0;i<N;i++) {
            int initial = scn.nextInt(), end = scn.nextInt(), weight = scn.nextInt();
            edges[i] = new edge(initial,end,weight);
        }
        kruskal_MinTree(edges,minTree);
        display(minTree);
    }
}

• 代码实现
• 测试运行