算法设计与分析——贪心算法——最优装载问题

电玩女神 2023-01-16 11:28 201阅读 0赞

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

#include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    
    typedef struct Node
    {
        
    	int number;//序列中的第几个 
    	int weight;//序列的重量 
    }node;
    bool cmp(node x,node y)
    {
        
    	if(x.weight<y.weight)
    		return true;
    	else
    		return false;
     } 
    void Loading(int *result,int *weight,int capacity,int n)
    {
        
    	Node node[n+1];
    	for(int i=1;i<=n;i++)
    	{
        
    		node[i].number=i;
    		node[i].weight=weight[i];
    	}
    	sort(node+1,node+n+1,cmp);
    	cout<<"货物按重量排好序为："; 
    	for(int i=1;i<=n;i++)
    	{
        
    		cout<<node[i].weight<<" ";
    		weight[i]=node[i].weight;
    	}
    	cout<<endl;
    	
    	for(int i=1;i<=n;i++)
    	{
        
    		result[i]=0;
    	}
    	int pre=1;
    	int c=capacity;
    	for(int i=1;i<=n;i++)
    	{
        
    		if(weight[i]<=c)
    		{
        
    			result[i]=1;
    			
    			c=c-weight[i];
    		}
    		else
    		{
        
    			break;
    		}
    	}
    	
    }
    int main()
    {
        
    	cout<<"输入集装箱的数量：";
    	int n;
    	cin>>n;
    	cout<<"输入轮船所能承担的最大重量：";
    	int capacity;
    	cin>>capacity;
    	cout<<"输入集装箱的重量序列：";
    	int weight[n+1];
    	for(int i=1;i<=n;i++)
    	{
        
    		cin>>weight[i];
    	}
    	
    	int result[n+1];
    	Loading(result,weight,capacity,n);
    	
    	for(int i=1;i<=n;i++)
    	{
        
    		cout<<result[i]<<" ";
    	}
    	
     }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: /images/20221022/e08aba9af28444efad1dbab949dff128.png