【贪心算法】最优装载问题C++语言

àì夳堔傛蜴生んèń 2023-03-12 12:13 152阅读 0赞

### 文章目录 ###

*   *   *  问题描述
         *  问题分析
         *  算法步骤
         *  举例
         *  代码

### 问题描述 ###

有一批集装箱要装上一艘重量为c的轮船。已知集装箱i（1<=i<=n）的重量为Wi，最优装载问题要求在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

### 问题分析 ###

抽象的数学模型为  
![在这里插入图片描述][20200508190416399.png]  
最优装载问题：n个集装箱E\{1,2，…n\}，选出E的子集合，将尽可能多的集装箱装上轮船  
![在这里插入图片描述][20200508190847575.png]  
贪心策略为重量最轻集装箱优先装载，从而给灭有装船的集装箱留下尽可能多的余量

### 算法步骤 ###

1、将集装箱按照重量的非减序排列  
2、依次从剩下的集装箱中选择重量最轻的货箱装船，直到所有集装箱均匀装上船或船上不能再容纳任何一个集装箱

### 举例 ###

n=8,W=\{100,200,50,90,150,50,20,80\},c=400  
解：所考察，货箱的次序为：7,3,6,8,4,1,5,2。

第一次贪心选择集装箱7装船，船上集装箱的总重量为20吨  
第二次贪心选择集装箱3装船，船上集装箱的总重量为70吨  
第三次贪心选择集装箱6装船，船上集装箱的总重量为120吨  
第四次贪心选择集装箱8装船，船上集装箱的总重量为200吨  
第五次贪心选择集装箱4装船，船上集装箱的总重量为290吨  
第六次贪心选择集装箱1装船，船上集装箱的总重量为390吨  
第七次贪心选择集装箱5装船，如果装船，超过最大载重量，因此算法停止  
![在这里插入图片描述][20200508193227469.png]  
6个集装箱1,3,4,6,7,8装船

### 代码 ###

//4d3 贪心算法 最优装载问题
    #include "stdafx.h"
    #include <iostream> 
    using namespace std; 
     
    const int N = 4;
     
    template <class Type>  
    void Swap(Type &x,Type &y); 
     
    template<class Type>
    void Loading(int x[],  Type w[], Type c, int n);
     
    template<class Type>
    void SelectSort(Type w[],int *t,int n);
     
    int main()
    {
        
    	float c = 400;
    	float w[] = {
        100,200,50,90,150,50,20,80};//下标从1开始
    	int x[N+1];
     
    	cout<<"轮船载重为："<<c<<endl;
    	cout<<"待装物品的重量分别为："<<endl;
    	for(int i=1; i<=N; i++)
    	{
        
    		cout<<w[i]<<" ";
    	}
    	cout<<endl;
    	Loading(x,w,c,N);
     
    	cout<<"贪心选择结果为:"<<endl;
    	for(int i=1; i<=N; i++)
    	{
        
    		cout<<x[i]<<" ";
    	}
    	cout<<endl;
     
    	return 0;
    }
     
    template<class Type>
    void Loading(int x[],Type w[], Type c, int n)
    {
        
    	int *t = new int [n+1];//存储排完序后w[]的原始索引
    	SelectSort(w, t, n);
     
    	for(int i=1; i<=n; i++)
    	{
        
    		x[i] = 0;//初始化数组x[]
    	}
    	for(int i=1; i<=n && w[t[i]]<=c; i++)
    	{
        
    		x[t[i]] = 1;
    		c -= w[t[i]];
    	}
    }
     
    template<class Type>
    void SelectSort(Type w[],int *t,int n)
    {
        
    	Type tempArray[N+1],temp;
    	memcpy(tempArray,w,(n+1)*sizeof(Type));//将w拷贝到临时数组tempArray中
    	int min;
     
    	for(int i=1;i<=n;i++)
    	{
        
    		t[i] = i;
    	}
     
    	for(int i=1;i<n;i++)
    	{
        
    		min=i;
    		for(int j=i+1;j<=n;j++)
    		{
        
    			if(tempArray[min]>tempArray[j])
    			{
        
    				min=j;
    			}
    		}
    		Swap(tempArray[i],tempArray[min]);
    		Swap(t[i],t[min]);
    	}
    }
     
    template <class Type>  
    void Swap(Type &x,Type &y)
    {
        
    	Type temp = x;  
        x = y;  
        y = temp;  
    }

[20200508190416399.png]: /images/20230312/5583e1e4970346f991d750556b777b0b.png
[20200508190847575.png]: /images/20230312/dede6c2dc4474ab081d6018ae093d040.png
[20200508193227469.png]: /images/20230312/c551250bd51b4c02b39c8f6452d82ebb.png