- 1、本文档共25页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
0-1背问题四种不同算法的实现
兰州交通大学
数理与软件工程学院
题 目 0-1背包问题算法实现
院 系 数理院
专业班级 信计09
学生姓名 雷雪艳
学 号 200905130
指导教师 李秦
二O一二年 六 月 五 日
一、问题描述:
1、0—1背包问题:给定n种物品和一个背包,背包最大容量为M,物品i的重量是wi,其价值是平Pi,问应当如何选择装入背包的物品,似的装入背包的物品的总价值最大?
背包问题的数学描述如下:
2、要求找到一个n元向量(x1,x2…xn),在满足约束条件:
情况下,使得目标函数,其中,1in;M0;wi0;pi0。满足约束条件的任何向量都是一个可行解,而使得目标函数达到最大的那个可行解则为最优解[1]。
给定n 种物品和1个背包。物品i 的重量是wi,其价值为pi,背包的容量为M。问应如何装入背包中的物品,使得装人背包中物品的总价值最大?在选择装人背包的物品时,对每种物品i只有两种选择,即装入背包、不装入背包。不能将物品i 装人背包多次,也不能只装入部分的物品i。该问题称为0-1背包问题。
0-1背包问题的符号化表示是,给定M0, w i 0, pi 0,1in ,要求找到一个n元0-1向量向量(x1,x2…xn), X i =0 或1 , 1in, 使得
,而且达到最大[2]。
二、解决方案:
方案一:贪心算法
1、贪心算法的基本原理与分析
贪心算法总是作出在当前看来是最好的选择,即贪心算法并不从整体最优解上加以考虑,它所作出的选择只是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广的许多问题它能产生整体最优解。在一些情况下,即使贪心算法不能得到整体最优解,但其最终结果却是最优解的很好近似解。
贪心算法求解的问题一般具有两个重要性质:贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
2、0-1背包问题的实现
对于0-1背包问题,设A是能装入容量为c的背包的具有最大价值的物品集合,则Aj=A-{j}是n-1个物品1,2,...,j-1,j+1,...,n可装入容量为c-wj的背包的具有最大价值的物品集合。
用贪心算法求解0-1背包问题的步骤是,首先计算每种物品单位重量的价值vi/wi;然后,将物品进行排序,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品总量未超过c,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直进行下去,直到背包装满为止。
3、算法设计如下:
#includeiostream.h
#define max 100 //最多物品数
void sort (int n,float a[max],float b[max]) //按价值密度排序
{
int j,h,k;
float t1,t2,t3,c[max];
for(k=0;kn;k++)
c[k]=a[k]/b[k];
for(j=0;jn;j++)
if(c[j]c[j+1])
{t1=a[j];a[j]=a[j+1];a[j+1]=t1;
t2=b[j];b[j]=b[j+1];b[j+1]=t2;
t3=c[j];c[j]=c[j+1];c[j+1]=t3;
}
}
void knapsack(int n,float limitw,float v[max],float w[max],int x[max])
{float c1; //c1为背包剩余可装载重量
int i;
sort(n,v,w); //物品按价值密度排序
c1=limitw;
for(i=0;in;i++)
{
if(w[i]c1)break;
x[i]=1; //x[i]为1时,物品i在解中
c1=c1-w[i];
}
}
void main()
{int n,i,x[max];
float v[max],w[max],totalv=0,totalw=0,limitw;
cout请输入n和limitw:;
cinn limitw;
for(i=1;i=n;i++)
x[i]=0;
您可能关注的文档
- (高一地一)定稿市一中必修二人文地理检测试题.doc
- (高一数科组)高一数学第一次月考试卷分析.doc
- (高一英)2010-2011学年第二学期期末质量监测高一英语科考试说明.doc
- (高一试)巨人中学2010学年第一学期第二次月考高一语文试卷.doc
- (高新二参加全国(陕西省)教育系统先进集体评选的材料)书香校园灵气氲、六艺课程翰墨香(定稿).doc
- (高层)手架专项施工方案(专家论证).doc
- (高新二参加雁塔区先进集体评选的材料)书香校园灵气氲、六艺课程翰墨香(定稿).doc
- (高二化试题]]高二化学选修五第三章《烃的含氧衍生物》单元测试题.doc
- (高滩小)2014学年第一学期学校工作总结.doc
- (高考)_难点06__函数值域及求法.doc
- 2023-2024学年广东省深圳市龙岗区高二(上)期末物理试卷(含答案).pdf
- 2023-2024学年贵州省贵阳市普通中学高一(下)期末物理试卷(含答案).pdf
- 21.《大自然的声音》课件(共45张PPT).pptx
- 2023年江西省吉安市吉安县小升初数学试卷(含答案).pdf
- 2024-2025学年广东省清远市九校联考高一(上)期中物理试卷(含答案).pdf
- 广东省珠海市六校联考2024-2025学年高二上学期11月期中考试语文试题.pdf
- 2024-2025学年语文六年级上册第4单元-单元素养测试(含答案).pdf
- 2024-2025学年重庆八中高三(上)月考物理试卷(10月份)(含答案).pdf
- 安徽省安庆市潜山市北片学校联考2024-2025学年七年级上学期期中生物学试题(含答案).pdf
- 贵州省部分校2024-2025学年九年级上学期期中联考数学试题(含答案).pdf
文档评论(0)