0-1背包问题、背包问题（贪心算法）

ゝ一世哀愁。 2022-06-18 01:56 186阅读 0赞

//
    //Description:0-1背包问题、背包问题（贪心算法）
    //
    #include <iostream>
    #include <iomanip>
    using namespace std;
    
    typedef float Status;
    typedef float Element;
    int num;//物品个数
    float c;//背包容量（即背包所能容纳的物品总重量）
    static  float value(0);//当前背包中所有货品的总价值
    
    class Object
    {
    public:
    	int id;
    	Element weight;
    	Element price;
    	Element avg_p;
    	Element in_knapsack_Weight;//该物品已经放入背包中的重量
    
    	void  avg_price()
    	{
    		avg_p = price / weight;
    	}
    };
    Object obj[6];//对象数组  ???如何动态的为对象数组分配内存空间？？？
    //目前可用物体数目为 5*******************
    
    void input(int n)
    {
    	for (int i = 1; i <= n; i++)
    	{
    		cout << "\n请依次输入第" << i << "个物体的重量和价格" << endl;
    		cin >> obj[i].weight >> obj[i].price;
    		obj[i].id = i;
    		obj[i].avg_price();
    	}
    	cout << endl;
    }
    void output(int n)
    {
    	for (int i = 1; i <= n; i++)
    	{
    		cout << "你所输入的第" << obj[i].id << "个物体的" << endl;
    		cout << "重量\t价格\t单价" << endl;
    		cout << obj[i].weight << "\t" << obj[i].price << "\t" << setprecision(4) << obj[i].avg_p;
    		//setprecision(n)用于显示n位有效位数，使用时必须引用头文件 iomanip.h 
    		cout << endl;
    	}
    }
    
    
    //将单价由高到低进行排序
    void compositor(int num)
    {
    	Object tem;
    
    	for (int j = 1; j < num; j++)
    	for (int i = 1; i <= num - j; i++)
    	{
    
    		if (obj[i].avg_p < obj[i + 1].avg_p)
    		{
    			tem = obj[i + 1];
    			obj[i + 1] = obj[i];
    			obj[i] = tem;
    		}
    	}
    }
    //往背包中放入物品,分为两种情况：
    //情况1 ：（0-1背包算法）所指定种类的物品要么全放进去要么一点儿都不放进去；
    //情况2 ：（背包算法）要么都可以放进去一部分或者全部.
    
    
    //情况1执行代码：
    
    void beibao_0_1(Status c, Status &value)
    {
    	value = 0;
    	int i = 0;
    	for ( i = 1; i <= num; i++)
    	{
    		if (obj[i].weight > c)
    			continue;
    		else
    		{
    			obj[i].in_knapsack_Weight = obj[i].weight;
    			value += obj[i].weight*obj[i].avg_p;
    			c -= obj[i].weight;
    		}
    	}
    
    
    	cout << "\n放入了背包中的物品情况如下\n";
    	for (i = 1; i <= num; i++)
    	{
    		if (obj[i].in_knapsack_Weight > 0)
    		{
    			cout << "\t物品" << obj[i].id << "放入的重量为 " << obj[i].in_knapsack_Weight << " ,其价值为 " << obj[i].price << endl;
    		}
    	}
    }
    
    //情况2执行代码：
    void beibao(Status c, Status &value)
    {
    	value = 0;
    	int i = 0;
    	for (i = 1; i <= num; i++)
    	{
    		if (obj[i].weight >= c)
    		{
    			obj[i].in_knapsack_Weight = c;
    			value += c*obj[i].avg_p;
    			break;
    		}
    		else
    		{
    			obj[i].in_knapsack_Weight = obj[i].weight;
    			value += obj[i].weight*obj[i].avg_p;
    			c -= obj[i].weight;
    		}
    	}
    
    
    	cout << "\n放入了背包中的物品情况如下\n";
    	for (i = 1; i <= num; i++)
    	{
    		if (obj[i].in_knapsack_Weight > 0)
    		{
    			Status z;
    			z = obj[i].in_knapsack_Weight*obj[i].avg_p;
    			cout << "\t物品" << obj[i].id << "放入的重量为 " << obj[i].in_knapsack_Weight << " ,其价值为 " << z << endl;
    		}
    	}
    }
    
    void chose_operator()
    {
    loop:
    	cout << "\n\t=========请选择一种算法============" << endl;
    	cout << "   1----- 0-1 背包算法   2-----背包算法   3(或者其他键)------Exit " << endl;
    	int n;
    	cin >> n;
    	switch (n)
    	{
    	case 1: 
    	      {//0-1背包算法
    			loop2:   cout << "\n=====0-1背包算法===== ";
    				beibao_0_1(c, value);
    				cout << "背包容量为 " << c << " ,背包内的物品总价值为 " << value << " 元\n\n";
    				cout << "想看一下另一种算法吗？（Y/N）\n";
    				char z;
    				cin >> z;
    
    				if (z - 'Y' == 0 || z - 'Y' == 32)
    				{
    					goto loop1;
    				}
    				else
    				if (z - 'N' != 0 || z - 'n' != 32)
    				{
    					cout << "您的输入有误！" << endl;
    				}
    	      }; break;
    	case 2: 
    	      {//背包算法
    		  loop1:    
    			    cout << "\n=====背包算法===== ";
    				beibao(c, value);
    				cout << "背包容量为 " << c << " ,背包内的物品总价值为 " << value << " 元\n";
    
    				cout << "想看一下另一种算法吗？（Y/N）\n";
    				char z;
    				cin >> z;
    
    				if (z - 'Y' == 0)
    				{
    					goto loop2;
    				}
    				else
    				if (z - 'N' != 0)
    				{
    					cout << "您的输入有误！,程序退出！" << endl;
    				}
    			}; break;
    	case 3: break;
    	default:
    	       {
    			   cout << "输入有误，请重试！\n";
    			   goto loop;
    	        }
    
    	}
    }
     
    void main()
    {
     	cout << "\n\t============贪心算法－背包问题============" << endl;
    	cout << "  请输入物品个数" << endl;
    	cin >> num;
    
    	input(num);
    	output(num);
    	compositor(num);
    	cout << "\n----------排序后：" << endl;
    	output(num);
    
    	cout << "\n   请输入背包的容量（kg）\n";
    	cin >> c;
    
    	chose_operator();
    }