贪心算法

实验项目名称：贪婪算法技术的应用

一、实验任务和要求

1、问题描述
2、设计问题求解的算法、并进行代码的编写、调试、运行。
3、分析算法的时间复杂度

二、算法描述

1）问题描述
a.活动安排问题
b.背包问题

2）算法描述：
a.活动安排问题：使用贪心算法，先按结束时间排序；第一个活动选择结束时间最早的；再选择开始时间晚于上一个活动的结束时间且结束时间最早的活动，重复该步骤。

#include <stdio.h>

// 结构体表示活动
struct Activity {
    int start;
    int end;
    int no; //活动号
};

// 按照活动结束时间升序排序
void sortByEndTime(struct Activity arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j].end > arr[j + 1].end) {
                // 交换活动的位置
                struct Activity temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// 打印选择的活动
void printActivities(struct Activity arr[], int n) {
    sortByEndTime(arr,n); // 按照活动结束时间升序排序
    printf("Selected Activities:\n");

    // 第一个活动总是被选中
    int i = 0; //记录上一个被选中的活动
    printf("(%d, %d) ", arr[i].start, arr[i].end);

    // 对剩余活动进行遍历
    for (int j = 1; j < n; j++) {
        // 如果当前活动的开始时间大于或等于前一个活动的结束时间，则选择该活动
        if (arr[j].start >= arr[i].end) {
            printf("(%d, %d) ", arr[j].start, arr[j].end);
            i = j;
        }
    }
}

int main() {
    // 示例活动
    struct Activity activities[] = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};

    // 计算活动数组的大小
    int n = sizeof(activities) / sizeof(activities[0]);

    // 打印选择的活动
    printActivities(activities, n);

    return 0;
}

b.背包问题：贪心算法,先按照价值密度（value/weight）降序排序，然后尽可能多地装入背包，分为整个装入和部分装入。0-1也按性价比排序

#include <stdio.h>

// 结构体表示物品
struct Item {
	int weight;//重量
	int value;//价值
};

// 按照价值密度（value/weight）降序排序
void sortByValueDensity(struct Item arr[], int n) {
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < n - i - 1; j++) {
			double density1 = (double)arr[j].value / arr[j].weight;
			double density2 = (double)arr[j + 1].value / arr[j + 1].weight;
			
			if (density1 < density2) {
				// 交换物品的位置
				struct Item temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

// 解决分数背包问题
double fractionalKnapsack(struct Item arr[], int n, int capacity) {
	sortByValueDensity(arr, n);
	
	double totalValue = 0.0;
	int currentWeight = 0;
	
	for (int i = 0; i < n; i++) {
		if (currentWeight + arr[i].weight <= capacity) {
			// 将整个物品放入背包
			currentWeight += arr[i].weight;
			totalValue += arr[i].value;
		} else {
			// 将物品的一部分放入背包
			double remainingCapacity = capacity - currentWeight;
			totalValue += (double)arr[i].value / arr[i].weight * remainingCapacity;
			break;
		}
	}
	
	return totalValue;
}

int main() {
	// 示例物品
	struct Item items[] = {{10, 60}, {20, 100}, {30, 120}};
	
	// 计算物品数组的大小
	int n = sizeof(items) / sizeof(items[0]);
	
	// 背包容量
	int capacity = 50;
	
	// 解决分数背包问题并输出结果
	double maxValue = fractionalKnapsack(items, n, capacity);
	printf("Maximum value in Knapsack = %.2lf\n", maxValue);
	
	return 0;
}

三、算法时间复杂度分析

a.按结束时间排序函数的时间复杂度为O(n^2^),打印选择活动函数的时间复杂度为O(n),故该算法时间复杂度为O(n^2^)。
b.按照价值密度（value/weight）降序排序函数的时间复杂度为 O(n^2^)，解决分数背包问题函数的时间复杂度为O(n),故该算法时间复杂度为O(n^2^)。

四、实验结果

五、实验心得

贪心算法每次的选择都是基于当前情况下的最优决策。它满足最优子结构的问题，即一个问题的最优解可以通过子问题的最优解来构建。贪心算法不一定能够得到全局最优解，但能够得到局部最优解。简单来说，贪心算法采取局部最优的决策，希望通过每个局部最优解的选择，最终得到全局的最优解。

Donate