背包问题贪心算法解决
更新时间:2023-08-08 08:08:01 阅读量: 实用文档 文档下载
贪心算法求解背包问题
一、 实验内容
有一个承重为W的背包和n个物品,它们各自的重量和价值分别是wi和vin
W wi求这些物品中最有价值的一个子集。如果每次选择某(1<=i<=n),设
i 1一个物品的时候,只能全部拿走,则这一问题称为离散(0-1)背包问题;如果每次
可以拿走某一物品的任意一部分,则这一问题称为连续背包问题。
二、 算法思想
首先计算出物品单位重量的价值vi/wi,并排序,依贪婪策略,从物品中选择可装入背包的vi/wi值最大的物品。若该物品装入背包后,背包中物品总重量未超过背包最大承重m,则选择单位重量价值次之的物品装入背包,依次策略进行下去,直到背包装满为止。
三、 实验过程(C++)
#include<iostream>
using namespace std;
//n表示背包可以存放物品的种类
//指针p指向存放物品价值的数组
//指针q指向存放物品重量的数组
void sort(int n,float *p,float *q)
{
int i;
int j;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if((*(p+i))/(*(q+i))<(*(p+j))/(*(q+j)))
{
float f;
f=*(p+i);
*(p+i)=*(p+j);
*(p+j)=f;
f=*(q+i);
*(q+i)=*(q+j);
*(q+j)=f;
}
}
void bag(int n,float m,float *v,float *w,float *x)
{
sort(n,v,w);
int i;
for(i=0;i<n;i++)
{
if(*(w+i)>m)
break;
*(x+i)=1;//可以存放该物品时,置1
m-=*(w+i);//放入后,背包的容量减少
}
//当此时背包的容量不够存放整个物品的情况时,存放一部分 if(i<n)
*(x+i)=m/(*(w+i));
if(*(x+i)!=1)
*(x+i)=0;
}
int main()
{
int m ,n,i;
cout<<"输入背包容量:"<<endl;
cin>>m;
cout<<"输入物品种类:"<<endl;
cin>>n;
float *w=new float[n];
float *v=new float[n];
float *x=new float[n];
cout<<"输入各种物品的重量:"<<endl;
for(i=0;i<n;i++)
cin>>w[i];//各种物品的重量
cout<<"输入各种物品的价值:"<<endl;
for(i=0;i<n;i++)
cin>>v[i];//各种物品的价值
for(i=0;i<n;i++)
*(x+i)=0;
bag(n,m,v,w,x);
cout<<"\n1表示要放入:"<<"\n0表示不放入:"<<endl; cout<<"物品容量内容:";
for(i=0;i<n;i++)
cout<<*(w+i)<<" ";
cout<<"\n物品价值内容:";
for(i=0;i<n;i++)
cout<<*(v+i)<<" ";
cout<<"\n物品存放情况:";
for(i=0;i<n;i++)
cout<<*(x+i)<<" ";
cout<<endl;
return 0;
}
四、 实验结论
输入背包容量:
50
输入物品种类:
3
输入各种物品的重量:
26 23 15
输入各种物品的价值:
18 15 10
1表示要放入:
0表示不放入:
物品容量内容:26 15 23
物品价值内容:18 10 15
物品存放情况:1 1 0
五、 算法复杂度分析
时间复杂度为O(n2);
Tsort = O(在此处键入公式。nlogn); Tf(for循环复杂度为) =n2;
T = sort + Tf = O(nlogn) + O(n2) = O(n2).
正在阅读:
背包问题贪心算法解决08-08
说明书06-06
图书信息管理的设计与实现(C课程设计)03-08
经济法案例整理 - 图文04-15
对当前纪检监察信访工作机制的研究和思考04-09
半年工作总结,半年工作总结范文_2022年上半年工作总结报告07-31
SWOT分析方法在农业产业发展战略研究中的应用——以湖南农产品加工业发展战略研究为例05-22
“小手拉大手,洁美我家园”03-18
大学普通化学复习知识点05-22
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 贪心
- 算法
- 背包
- 解决
- 问题