2贪心算法解决部分背包问题
2贪心算法解决部分背包问题
一、实验目的
学习掌贪心算法法思想。
二、实验内容
用贪心法解决部分背包问题。给定n种物品和一个背包。物品i的重量是Wi,其价值为pi,背包的容量为M,将物品i的一部分xi放入背包会得到pi xi的效益。应如何选择装入背包的物品,使得装入背包中物品的总价值最大?给出具体的装包方案。在选择装入背包的物品时,对每种物品i,可以整件装入背包、不装入背包或部分装入背包。但不能将物品i装入背包多次。
四、需求分析
对于给定n种物品和一背包。在容量最大值固定的情况下,要求装入的物品价值最大化。
五、基本思想:
贪婪法是解决最优化问题时的一种简单但适用范围有限的策略。总是对当前的问题作最好的选择,也就是局部寻优。最后得到整体最优。总是选择单位价值最高的物品。
六、详细设计
#include
using namespace std;
struct _Object//物品结构体
{
int Value;//物品价值
int Weight;//物品重量
int AveValue;//物品单位价值
float Num;//物品可以放入的数量
void knaspsack(int n,float M,_Object object[])
{ //n为物品个数,M为背包容量
int i;
float C=M;
for(i=0;i{
object[i].Num=0;//初始化放入背包的物品为0
if(object[i].Weight>C)break;//当物品重量大于背包容量时
else//小于时
{
object[i].Num=1;//物品i放入一件
C-=object[i].Weight;//背包容量减小
}
}
if(i<=n)//当不能放入整个物品时,选取物品一部分放入
object[i].Num=C/object[i].Weight;
for(i=0;i{
if(object[i].Num>0)
cout<<"重量为: "<