koudai2.cpp

包含了01背包和非01背包两个程序！是我一次作业完成的

//  我保证这次作业是我个人独立完成没有抄袭他人作业和代码

#include<iostream>
#include<string>
using namespace std;

// 定义一个结构 记录数据
struct packet
{
	int value;   // 记录每个物品的价值
	int size;    // 记录每一个物品的大小
}temp[100];     // 定义最多有100个物品

// compare 函数    
// 按照 单位大小所含有的价值进行排列
int compare(const void *a ,const void *b)
{
	return ((packet *)b)->value*((packet *)a)->size - ((packet * )b)->size*((packet *)a)->value;
}

int msize,num;//  记录口袋的最大可成放的 msize  已经所有物品的数目

// 定义一个函数  用于设置数据 
void set()
{
	cout<<"please input the totle size of the bag"<<endl;
	cin>>msize;
	cout<<"please input the number of the bags"<<endl;
	cin>>num;
	cout<<"please input the size and the value of each bag"<<endl;
	for(int i=0;i<num;i++)
	{
		cin>>temp[i].size>>temp[i].value;
	}
	
}

// 主要的计算函数
void funtion()
{
	int l = msize;  //口袋当前所能够容纳的大小
	double c=0;     // 当前口袋内物品的总价值
	//  现比较一下
	qsort(temp,num,sizeof(packet),compare);

	for(int i=0;i<num;i++)
	{
		if(temp[i].size<= l)   //  如果口袋可以成放 temp[i]时  就操作
		{
			c+=temp[i].value;  // 总价值增加
			l=l-temp[i].size;  // 相当口袋的大小也要减小
		}
		//   下面是利用物品的可分性    如果口袋的可容量已经小于temp[i]
		//    就要对其进行分割   取出l 大小的物品 
		else
		{
			c+=temp[i].value*l/temp[i].size;
			l=0;
		}
		if(l==0) break;    //如果口袋已经装满了  就要结束了
	}
	cout<<c<<endl;
}

//  在主函数中分别调用两个函数 
void main()
{
	set();
	funtion();
}