算法设计与分析——贪心算法——背包问题

谁践踏了优雅 2023-01-16 09:35 161阅读 0赞

**0-1背包问题：**  
前提：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。  
问题：应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

**背包问题：**  
与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。

贪心算法总是做出在当前看来是最好的选择，也就是说，贪心算法并不从整体最优上加以考虑，所做出的的选择只是某种意义上的局部最优选择；  
虽然贪心算法不是对所有的问题都能得到整体最优解，但对范围相当广的许多问题都能产生最优解，即使贪心算法不能得到整体最优解，但其最终结果却是最终结果却是最优解的很好的近似解。

注意：不要用if else

#include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    
    typedef struct Node
    {
        
    	float value;
    	float weight;
    	float vw;//单位重量的价值 
    }node;
    bool cmp(node x,node y)
    {
        
    	if(x.vw>y.vw)//从大到小排序 
    		return true;
    	else
    		return false;
    }
    void knaspsack(int n,float capacity,float *value,float *weight,float *result)
    {
        
    	Node node[n+1];
    	for(int i=1;i<=n;i++)
    	{
        
    		node[i].value=value[i];
    		node[i].weight=weight[i];
    		node[i].vw=(float)node[i].value/node[i].weight;
    		
    	}
    	
    	sort(node+1,node+n+1,cmp);
    	for(int i=1;i<=n;i++)
    	{
        
    		value[i]=node[i].value;
    		cout<<value[i]<<" ";
    		weight[i]=node[i].weight;
    		
    		cout<<weight[i]<<" ";
    		
    		cout<<node[i].vw<<endl;
    	}
    	
    	float c=capacity;
    
    	int i;
    	for(int i=1;i<=n;i++)
    	{
        
    		if(c<=weight[i])
    				break;
    		//这里不能使用if else 
    		result[i]=1;
    		c=c-weight[i];
    		
    	}
    	
    	if(i<=n)
    	{
        		
    		result[i]=c/weight[i];		
    	}
    }
    void knapsack(int n,float M,float v[],float w[],float x[])  
    {
          
        int i;  
        //物品整件被装下  
        for(i=1;i<=n;i++)
        {
          
            if(w[i]>M) break;   
            x[i]=1;  
            M-=w[i];  
        }   
        //物品部分被装下  
        if(i<=n) x[i]=M/w[i];   
    } 
    int main()
    {
        
    	cout<<"输入背包中物品的种类：";
    	int n;
    	cin>>n; 
    	cout<<"输入背包的容量";
    	float capacity;
    	cin>>capacity; 
    	cout<<"输入物品对应的价格：";
    	float value[n+1]; 
    	for(int i=1;i<=n;i++)
    	{
        
    		cin>>value[i];
    	}
    	cout<<"输入物品对应的重量：";
    	float weight[n+1];
    	for(int i=1;i<=n;i++)
    	{
        
    		cin>>weight[i];
    	 }
    	 float result[n+1];
    	 	for(int i=1;i<=n;i++)
    	{
        
    		result[i]=0;
    	}
    	 //knaspsack(n,capacity,value,weight,result);
    	 knapsack(n,capacity,value,weight,result);
    	 for(int i=1;i<=n;i++)
    	 {
        
    	 	cout<<result[i]<<" ";
    	 	
    	 }
    	  return 0;
     }

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

![在这里插入图片描述][20210426190915923.png]  
贪心算法解决背包问题的主要时间用在了将其各种物品按其单位重量的价值从小到大排序 O(n\*logn)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: /images/20221022/787638c9ec4642839eecff208b83b7e9.png
[20210426190915923.png]: /images/20221022/3dcf84176bc2405cba95e423d3f9d167.png