算法设计与分析 实验三 贪心算法

1、掌握贪心算法的基本思想。
2、学习利用贪心算法设计和实现算法的方法。
3、了解利用替换法证明贪心策略是否能获得全局最优解的过程。
4、熟练掌握贪心算法在两个典型图搜索中的应用，即单源最短路径和最小生成树算法中，利用合理的数据结构优化算法复杂度的技巧。

1、问题描述：利用贪心法来设计并实现最优装载问题
2、问题描述：利用贪心法来设计并实现单源最短路径。
3、问题描述：字符a~h出现的频率恰好是前n个Fibonacci数，它们的哈夫曼编码是什么？扩展到前n个字符的频率恰好是前n个Fibonacci数的情形。写程序实现。

问题描述：有一批集装箱要装上一艘载重量为C的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

#include
int main(){
	int n = 0; 
	int max_weight;
	scanf("%d",&max_weight);	//输入轮船的载重量 
	scanf("%d",&n);				//输入集装箱的数量 
	int a[n] = {0};
	for(int i = 0;i < n; i++){	//将每个集装箱的重量存入数组a[n]中 
		scanf("%d",&a[i]);
	}
	
	for(int i= 0;i < n; i++){   //用冒泡排序将货物从小到大排列
        for(int j = 0;j < i;j++){
            if(a[j]>a[j+1]){
                int temp = 0;
                temp = a[j+1];
                a[j+1] = a[j];
                a[j] = temp;
            }
        }
    }

	int b[n] = {0};				//用数组b[n]记录能装入轮船的集装箱 
	for(int i = 0;i < n;i++){
		max_weight = max_weight - a[i];	
		if(max_weight > 0){	//还大于零就代表轮船还能继续装集装箱 
			b[i] = a[i];		//装进一个，数组b就记录一个 
		} 
	}

	for(int i = 0;i < n; i++){
        if(b[i] != 0){
            printf("%d ",b[i]);
        }
    }
	
}

剩下的明天写