文档库 最新最全的文档下载
当前位置:文档库 › 0_1背包问题的贪心算法_黄宇林

0_1背包问题的贪心算法_黄宇林

0_1背包问题的贪心算法_黄宇林
0_1背包问题的贪心算法_黄宇林

收稿日期:2006-02-14

作者简介:黄宇林(1965-),男,湖北鄂州人,鄂州大学基础科学系讲师,研究方向:数学教育。

第13卷第6期

Vol.13No.6鄂州大学学报

JournalofEzhouUniversity

2006年11月Nov.2006

1问题的提出

背包问题分为部分背包问题和0/1背包问题两种。部分背包问题在选择物品时,可以将物品分割为部分装入背包,即0≤xi≤1[1],很显然属于贪心算法的范畴,用贪心算法能较好地解决其求解。下面来讨论0/1背包问题。

0/1背包问题:设有n种东西可以装入背包,wj

是第j种东西的重量,vj是它的价值,xj是装入背包中的第j种东西的个数,设b(b>0)是背包总重量的

最大值,则背包问题可表示为:

设FK(y)是背包中只装第k种东西,总重量限制为y的情况下所具有的最大值,即

Fk(y)=maxk

j=1

"vjxj

(0#k#n)k

j=1

"wjxj

#y

(0#y#b)

不难看出背包问题满足优化原则,我们可以使用动态规划的方法,所得的递推等式和边界条件是:

Fk(y)=maxFk-1(y),Fk(y-wk)+vk$%F0(y)=0,对于一切y,0#y#bFk(0)=0,对于一切k,0#k#n

为了求解的方便,定义y为负数时,Fk(y)=-

[2]

用动态规划求解是理所当然的,同时我们知道在一般情况下,贪心算法不适于解0/1背包问题,但在特殊的情况下,用贪心算法也能解决部分0/1背包问题,而且求解非常简洁。

2动态规划与贪心算法的区别与联系2.1联系

都是通过局部最优解得到整体最优解。

2.2区别

贪心算法是指从问题的初始状态出发,通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法,贪心策略总是做出在当前看来最优的选择,并不是从总体上加以考虑,它所做的选择只是在某种意义上的局部最优解。

它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一

个规模更小的子问题,通过每一步贪心选择,最终可得到问题的一个最优解[3]。

动态规划是在每一步判断的时候只须考虑与它有关的前一步的情况而与以前的各步的判断没有关系,解决这类问题的方法是:把问题化成多步判断的问题,在每步作出判断时,只考虑由初始决策所确定的当前状态。

它采用自底向上的顺序,找到边界条件,将整个问题的最优解与问题的局部最优解用递推的等式联系起来,把边界条件代入递推等式逐步求得最优解。

30/1背包问题的贪心算法

背包问题有多种贪婪策略,每种策略都需经

0/1背包问题的贪心算法

黄宇林

(鄂州大学基础科学系,湖北鄂州436000)

摘要:0/1背包问题属于动态规划问题,部分背包问题属于贪心算法的范畴,通过比较两种算法的联系和区别,来寻求0/1背包问题的贪心算法的条件,用贪心算法来解决部分0/1背包问题的求解。

关键词:动态规划;贪心算法;0/1背包问题中图分类号:O223

文献标识码:A

文章编号:1008-9004(2006)06-0038-03

max

第6期黄宇林:0/1背包问题的贪心算法

过多个步骤完成,每一步要用贪婪准则选择一个

物品装入背包。

一种贪婪准则为:从剩余的物品中,选出可以

装入背包的价值最大的物品,然后是下一个价值

最大的物品,如此下去(在容量范围内),这种策略

不能保证得到最优解。例如,考虑n=3,w=

[100,10,10],v=[20,15,25],p=105。利用价值贪婪准

则时,得到的解为x=[1,0,0],总价值为20,而最优解

为X=[0,1,1],其总价值为40。

另一种是重量贪婪准则,从剩下的物品中选

择可装入背包的重量最小的物品。这种准则对上

面的例子能得到最优解,但在一般情况下,不一定

能得到最优解。考虑n=4,w=[2,3,4,7]v=[1,3,5,9],p=

10。利用重量贪婪准则得到解为x=[1,1,1,0],比最优

解[0,1,0,1]要差。

第三种贪婪准则是价值密度(vi/wi)贪心算法,

这种准则为:从剩余物品中选可装入的价值密度

(vi/wi)值最大的物品。

40/1背包问题适应的贪心策略

从上面几种贪心策略来看,前两种策略显然

不适于解0/1背包问题,而第三种价值密度贪婪算

法能较好地解决上面两个例子。从0/1背包问题来

看,在背包的容量范围内,当然是单位价值密度vi/

wi越大,才越接近最优解,故利用价值密度贪婪算

法能直接或经过改进后能解决部分0/1背包问题。

下面给出一个定理:

定理1:设wi>0,vi背包总重量限制为b,v1≥v2≥

…≥vn,w1≥w2≥…≥wn,且满足v1

w1≥v2

w2

≥…≥vn

wn

[4],则

(1)若w1+wp+…+wq=b时(1≤p≤q<n),则最优

解X=[1,0,…,0,1

第p个,0,…,0,1

第p个

,0,…,0]。

(2)若w1+wp+…+wq<b时(1≤p≤q<n),若

Ewq+1+wq+2+…>wq使得w1+wp+…+wq+wq+1+wq+2+…<b则vq+1+vq+2+…>vq则最优解X=[1,0,…,0,1

第p个

,0,…,

0,1

第p+1个,1

第p+2个

,…,1,0,…,0];否则最优解为X=

[1,0,…,0,1

第p个,0,…,0,1

第q个

,0,…,0]。

证明:(1)的条件完全符合贪心算法,结论是

显然的。

(2)若Ewq+1+wq+2+…>wq使得w1+wp+…+wq+1+wq+2+

…<b则vq+1+vq+2+…>vq时,使用贪心算法所得到的解

为较优解,而不是最优解,X=[1,0,…,0,1

第p个

,0,…,0,

第q个

,0,…,1,0,…,0]为较优解,最优解应为X=[1,0,…,

0,1

第p个

,0,…,0,1

第q+1个

,1

第q+2个

,…,1,0,…,0]。若不存在wq+1+

wq+2+…>wq使得w1+wp+…+wq+1+wq+2+…<b且vq+1+vq+2+

…>vq时,此时的解为最优解。即X=[1,0,…,0,1

第p个

,0,

…,0,1

第q个

,0,…,1,0,…,0]。

例1设背包重量的限制b=10,四种物品的重

量和价值如下:

v1=9,v2=5,v3=3,v4=1

w1=7,w2=4,w3=3,w4=2

显然

v1

w1

≥v2

w2

≥v3

w3

≥v4

w4

第一步:取第一种物品w1=7,余下w3=3,第二

种物品不够,

第二步:取第三种物品w3=3,且w1+w3=b

故得最优解x=[1,0,1,0]

例2设背包重量限制b=10,五种物品重量和

价值如下:

v1=9,v2=5,v3=2.5,v5=1.5

w1=7,w2=4,w3=3,w4=1.7,w5=1.2,

显然

v1

w1

≥v2

w2

≥v3

w3

≥v4

w4

≥v5

w5

第一步:取第一种物品w1=7,余3

第二步:取第三种物品w3=2,w1+w3=9<b,但此

时w4+w5>w3,且w1+w4+w5<b,v4+v5>v3

则得到最优解为X=[1,0,0,1,1]

5小结

0/1背包问题属于动态规划范畴,而对于符合

上述条件的0/1背包问题运用贪心算法也能求出其

最优解,且求解过程比动态规划算法快得多,因

此,能用贪心算法求解的0/1背包问题就不必再使

用动态规划算法了。

39

鄂州大学学报第13卷

【参考文献】

[1]方世昌.离散数学[M].西安:西安电子科技大学出版社,1996.

[2]王兵山,琴长英,周贤林,等.离散数学[M].长沙:国防科技大学出版社,1985:302-305.[3]王元香,李尚奋.离散数学[M].北京:科学出版社,1994.

Surplusnotationalsysteminadditionlogicunitdesignapplication

WUQiong

(ComputerDepartment,EzhouUniversity,Ezhou,Hubei436000,China)

Abstract:AdditionLogicunitisoneofthemostbasicunitsinacomputerchipdesign.Binarysystemisgenerallyappliedtothe

computerarithmeticoperations,thisarticleanalysedtheprincipleofsurplusnotationalsystem,anddemonstratedthefeasibilityandadvantagesaswellassomequestionswhichwillprobablyariseintheeventthatsurplusnotationalsystemtakestheplaceofbinarysysteminadditionlogicunitdesign.

Keywords:additionlogicunitdesign;binarysystem;surplusnotationalsystem

【参考文献】

[1]苏德富,钟诚.计算机算法设计与分析[M].北京:电子工业出版社,2001:60-62.[2]屈婉玲.组合数学[M].北京:北京大学出版社,2001:174-177.

[3]朱洪.算法设计与分析[M].上海:上海科学技术文献出版社,1989:162-163.[4]屈婉玲.组合数学[M].北京:北京大学出版社,2001:192-195.

Greedyalgorithmforthesolutionofthequestionof0/1knapsack

HUANGYu-lin

(BasicScienceDepartment,EzhouUniversity,Ezhou,Hubei436000,China)

Abstract:Thequestionof0/1knapsackissolvedthroughdynamicplanning,butpartofsuchaproblemcanbesolvedbygreedy

algorithm.Explainingthedifferencesandsimilaritiesoftheabovetwomethods,thearticleaimstoelaboratetheconditionswherethequestionof0/1knapsackcanbesolvedbygreedyalgorithm.

Keywords:dynamicplanning;greedyalgorithm;thequestionof0/1knapsack

(上接第27页)

40

贪心算法0-1背包问题(算法实验代码)

实验三、0-1背包问题(贪心算法) 实验代码: #include int max(int a,int b) { if(a>b) return a; else return b; } void Knapsack(int *v,int *w,int *x,int c,int n, int m[8][100]) { int i,j; for(j=0;j=1;i--) { for(j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } for(i=1;i

printf("物品总数为:7\n"); printf("物品重量和价值分别为:\n"); printf("\n重量价值\n"); for (i=1;i<=n;i++) printf("%d %d \n",w[i],v[i]); int m=15; int array[8][100]={0}; Knapsack(v,w,x,m,7,array); printf("背包能装的最大价值为: %d\n",array[1][m]); printf("贪心算法的解为: "); for(i=1;i<=n;i++) { if(i==1) printf("%d",x[i]); else printf(" %d",x[i]); } printf("\n"); return 0; } 测试截图为:

算法设计实验_贪心算法背包问题

《算法分析与设计》 课程实验 专业年级:信息与计算科学 学生学号: 学生姓名: 实验题目:用贪婪法求解背包问题 指导老师: 实验时间:20xx年xx月x日 一、实验内容 用贪婪法求解背包问题 要求:用非递归实现 二、实验步骤 2.1、理解算法思想和问题要求; 2.2、写出每个操作的算法 非递归算法: greedbag() { int N; int c;

int[] w; int[] v; Scanner scan=new Scanner(System.in); System.out.print("输入背包的容量:"); c=scan.nextInt(); System.out.print("输入物品的数量:"); N=scan.nextInt(); System.out.print("分别输入物品的价值:"); v=new int[N]; for(int i=0;i

【精选】贪心算法的应用

贪心算法的应用 课程名称:算法设计与分析 院系:计算机科学与信息工程学院 学生姓名:**** 学号:********** 专业班级:********************************** 指导教师:****** 201312-27

贪心算法的应用 摘要:顾名思义,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。当然,希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。如单源最短路经问题,最小生成树问题等。在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。贪心算法求问题一般具有两个重要性质:贪心选择性质和最优子结构性质。所谓贪心选择性是指所求问题的整体最优解可以通过一系列局部最优解的选择,即贪心选择达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法主要区别。当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 背包问题是一个经典的问题,我们可以采用多种算法去求解0/1背包问题,比如动态规划法、分支限界法、贪心算法、回溯法。在这里我们采用贪心法解决这个问题。 关键词:贪心法背包问题最优化

目录 第1章绪论 (3) 1.1 贪心算法的背景知识 (3) 1.2 贪心算法的前景意义 (3) 第2章贪心算法的理论知识 (4) 2.1 问题的模式 (4) 2.2 贪心算法的一般性描述 (4) 第3章背包问题 (5) 3.1 问题描述 (5) 3.2 问题分析 (5) 3.3算法设计 (5) 3.4 测试结果与分析 (10) 第4章结论 (12) 参考文献 (13) 附件 (13)

C语言版贪心算法背包问题

#include<> #define N 100 typedef struct bao{ int num; float w; float v; }; typedef struct avg{ int num; ( float val; float w; float v; }; struct bao b[N]; struct avg d[N]; int n; float c; ^ void Sort() { int i,j,k; struct avg temp[N]; for(i=0;i

float x[N],sum = 0; for(i=0;ic) break; x[d[i].num] = 1; sum += d[i].v; c -= d[i].w; } if(i

背包问题贪心法

背包问题贪心法 实验报告 学院:计算机科学与技术学院班级:**** 学号:**** 姓名:****

一、实验目的 1)以背包问题为例,掌握贪心法的基本设计策略。 2)熟练掌握各种贪心策略情况下的背包问题的算法并实现;其中:量度标准分别取:效益增量P 、物品重量w 、P/w 比值; 3) 分析实验结果来验证理解贪心法中目标函数设计的重要性。 二、问题基本思想描述 (1)贪心法的基本思路 从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。 该算法存在问题: 1. 不能保证求得的最后解是最佳的; 2. 不能用来求最大或最小解问题; 3. 只能求满足某些约束条件的可行解的范围。 (2)背包问题的描述 已知有n 种物品和一个可容纳M 重量的背包,每种物品i 的重量为i w 。假定将物品i 的一部分 i x 放入背包就会得到 i i x p 的效益,这里, 1 0≤≤i x , >i p 。 显然,由于背包容量是M ,因此,要求所有选中要装入背包的物品总重量不得超过M.。如果这n 件物品的总重量不超过M ,则把所有物品装入背包自然获得最大效益。现需解决的问题是,在这些物品重量的和大于M 的情况下,该如何装包,使得得到更大的效益值。由以上叙述,可将这个问题形式表述如下: 极 大 化目标函数 ∑≤≤n i i x p 1i 约束条件 M x w n i i ≤∑ ≤≤1i n i w p x i i i ≤≤>>≤≤1,0,0,10 (3)用贪心策略求解背包问题 首先需确定最优的量度标准。这里考虑三种策略:

背包问题(贪心算法)

算法分析与设计实验报告 第 4 次实验

}

附录:完整代码 #include #include #include struct node{ float value; float weight; }; float Value,curvalue=0; float Weight,curweight=0; //按价重比冒泡排序 void sort(node Node[],int M){ int i,j; node temp; for(i=0;i

贪心算法背包问题

算法设计与分析实验报告 题目:贪心算法背包问题 专业:JA V A技术xx——xxx班 学号: 姓名: 指导老师:

实验三:贪心算法背包问题 一、实验目的与要求 1、掌握背包问题的算法 2、初步掌握贪心算法 二、实验题: 问题描述:与0-1背包问题相似,给定n种物品和一个背包。物品i的重量是wi,其价值为vi,背包的容量为c。与0-1背包问题不同的是,在选择物品i装入背包时,背包问题的解决可以选择物品i的一部分,而不一定要全部装入背包,1< i < n。 三、实验代码 import java.awt.*; import java.awt.event.*; import javax.swing.*; public class er extends JFrame { private static final long serialVersionUID = -1508220487443708466L; private static final int width = 360;// 面板的宽度 private static final int height = 300;// 面板的高度 public int M; public int[] w; public int[] p; public int length; er() { // 初始Frame参数设置 this.setTitle("贪心算法"); setDefaultCloseOperation(EXIT_ON_CLOSE); setSize(width, height); Container c = getContentPane(); c.setLayout(new BoxLayout(c, BoxLayout.Y_AXIS)); setLocation(350, 150); // 声明一些字体样式 Font topF1 = new Font("宋体", Font.BOLD, 28); Font black15 = new Font("宋体", Font.PLAIN, 20); Font bold10 = new Font("宋体", Font.BOLD, 15); // 声明工具栏及属性设置 JPanel barPanel = new JPanel(); JMenuBar topBar = new JMenuBar(); topBar.setLocation(1, 1); barPanel.add(topBar); // 面板1和顶部标签属性设置 JPanel p1 = new JPanel(); JLabel topLabel = new JLabel("背包问题");

用贪心法求解0-1背包问题

算法设计与分析期末论文 题目用贪心法求解“0-1背包问题”专业计算机科学与技术 班级09计算机一班 学号0936021 姓名黄帅 日期2011年12月28日

一、0-1背包问题的算法设计策略分析 1.引言 对于计算机科学来说,算法的概念是至关重要的,例如,在一个大型软件系统的开发中,设计出有效的算法将起决定性的作用。算法是解决问题的一种方法或一个过程。程序是算法用某种设计语言具体实现描。计算机的普及极大的改变了人们的生活。目前,各行业、各领域都广泛采用了计算机信息技术,并由此产生出开发各种应用软件的需求。为了以最小的成本、最快的速度、最好的质量开发出适合各种应用需求的软件,必须遵循软件工程的原则。设计一个高效的程序不仅需要编程小技巧,更需要合理的数据组织和清晰高效的素算法,这正是计算机科学领域数据结构与算法设计所研究的主要内容。 2. 算法复杂性分析的方法介绍 算法复杂性是算法运行所需要的计算机资源的量,需要时间资源的量称为时间复杂性,需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N 、I 和A 表示算法要解问题的规模、算法的输入和算法本身,而且用C 表示复杂性,那么,应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开,并分别用T 和S 来表示,则有: T=T(N,I)和S=S(N,I) 。(通常,让A 隐含在复杂性函数名当中 最坏情况下的时间复杂性: 最好情况下的时间复杂性: 平均情况下的时间复杂性: 其中DN 是规模为N 的合法输入的集合;I*是DN 中使T(N, I*)达到Tmax(N)的合法输入; 是中使T(N, )达到Tmin(N)的合法输入;而P(I)是在算法的应用中出现输入I 的概率。 算法复杂性在渐近意义下的阶: 渐近意义下的记号:O 、Ω、θ、o 设f(N)和g(N)是定义在正数集上的正函数。 O 的定义:如果存在正的常数C 和自然数N0,使得当N ≥N0时有f(N)≤Cg(N),则称函数f(N)当N 充分大时上有界,且g(N)是它的一个上界,记为f(N)=O(g(N))。即f(N)的阶不高于g(N)的阶。 根据O 的定义,容易证明它有如下运算规则: (1)O(f)+O(g)=O(max(f,g)); (2)O(f)+O(g)=O(f+g); (3)O(f)O(g)=O(fg); (4)如果g(N)=O(f(N)),则O(f)+O(g)=O(f); (5)O(Cf(N))=O(f(N)),其中C 是一个正的常数; ∑∈= N D I I N T I P (N)T ),()(avg ∑∑∈==N D I k i i i I N e t I P ),()(1),(min min I N T (N)T N D I ∈=),(min 1I N e t k i i i D I N ∑=∈=)~,(1I N e t k i i i ∑==)~,(I N T =),(max max I N T (N)T N D I ∈=),(max 1I N e t k i i i D I N ∑=∈=),(*1I N e t k i i i ∑==) ,(*I N T =

0-1背包问题的算法设计策略对比与讲解

算法设计与分析大作业 班级:电子154 姓名:吴志勇 学号: 1049731503279 任课老师:李瑞芳 日期: 2015.12.25

算法设计与分析课程论文 0-1背包问题的算法设计策略对比与分析 0 引言 对于计算机科学来说,算法的概念是至关重要的。在一个大型软件系统的开发中,设计出有效的算法将起到决定性的作用。通俗的讲,算法是解决问题的一种方法。也因此,《算法分析与设计》成为计算科学的核心问题之一,也是计算机科学与技术专业本科及研究生的一门重要的专业基础课。算法分析与设计是计算机软件开发人员必修课,软件的效率和稳定性取决于软件中所采用的算法;对于一般程序员和计算机专业学生,学习算法设计与分析课程,可以开阔编程思路,编写出优质程序。通过老师的解析,培养我们怎样分析算法的“好”于“坏”,怎样设计算法,并以广泛用于计算机科学中的算法为例,对种类不同难度的算法设计进行系统的介绍与比较。本课程将培养学生严格的设计与分析算法的思维方式,改变随意拼凑算法的习惯。本课程要求具备离散数学、程序设计语言、数据结构等先行课课程的知识。 1 算法复杂性分析的方法介绍 算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上,所需的资源越多,该算法的复杂性越高;反之,所需资源越少,该算法的复杂性越低。对计算机资源,最重要的是时间与空间(即存储器)资源。因此,算法的复杂性有时间复杂性T(n)与空间复杂性S(n)之分。 算法复杂性是算法运行所需要的计算机资源的量,这个量应集中反映算法的效率,并从运行该算法的实际计算机中抽象出来,换句话说,这个量应该只依赖要解决的问题规模‘算法的输入和算法本身的函数。用C表示复杂性,N,I和A表示问题的规模、算法的输入和算法本身规模,则有如下表达式: C=F(N,I,A) T=F(N,I,A) S=F(N,I,A) 其中F(N,I,A)是一个三元函数。通常A隐含在复杂性函数名当中,因此表达式中一般不写A。 即:C=F(N,I) T=F(N,I) S=F(N,I) 算法复杂性中时间与空间复杂性算法相似,所以以下算法复杂性主要以时间复杂性为例: 算法的时间复杂性一般分为三种情况:最坏情况、最好情况和平均情况。下面描述算法复杂性时都是用的简化的复杂性算法分析,引入了渐近意义的记号O,Ω,θ,和o。 O表示渐近上界Ω表示渐近下界: θ表示同阶即:f(n)= O(g(n))且 f(n)= Ω(g(n)) 2 常见的算法分析设计策略介绍 2.1 递归与分治策略 分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。 递归算法举例: 共11页第1页

c应用贪心算法求解背包问题

实验五应用贪心算法求解背包问题 学院:计算机科学与技术专业:计算机科学与技术 学号:班级:姓名: 、 实验内容: 背包问题指的是:有一个承重为W的背包和n个物品,它们各自的重量和价值分别是n ,假设W w i和v i(1 i n)w i 1i,求这些物品中最有价值的一个子集。如果每次选择某一个物品的时候,只能全部拿走,则这一问题称为离散(0-1)背包问题;如果每次可以拿走某一物品的任意一部分,则这一问题称为连续背包问题。 二、算法思想: 首先计算每种物品单位重量的价值Vi/Wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去,直到背包装满为止。 三、实验过程: #in elude using n amespace std; struct goodi nfo

{ float p; // 物品效益 float w; // 物品重量 float X; // 物品该放的数量 int flag; // 物品编号 };// 物品信息结构体 void Insertionsort(goodinfo goods[],int n)// 插入排序,按pi/wi 价值收益进行排序,一般教材上按冒泡排序 { int j,i; for(j=2;j<=n;j++) { goods[0]=goods[j]; i=j-1; while (goods[0].p>goods[i].p) { } goods[i+1]=goods[0]; } }// 按物品效益,重量比值做升序排列goods[i+1]=goods[i]; i--; void bag(goodinfo goods[],float M,int n) { float cu; int i,j;

贪心算法详解分析

贪心算法详解 贪心算法思想: 顾名思义,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。当然,希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。如单源最短路经问题,最小生成树问题等。在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。 贪心算法的基本要素: 1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。 2. 当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的 最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 贪心算法的基本思路: 从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时,算法停止。 该算法存在问题: 1. 不能保证求得的最后解是最佳的; 2. 不能用来求最大或最小解问题; 3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程: 从问题的某一初始解出发; while 能朝给定总目标前进一步do 求出可行解的一个解元素; 由所有解元素组合成问题的一个可行解; 用背包问题来介绍贪心算法: 背包问题:有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。要 求尽可能让装入背包中的物品总价值最大,但不能超过总容量。

背包问题-贪心法和动态规划法求解

实验四“0-1”背包问题 一、实验目的与要求 熟悉C/C++语言的集成开发环境; 通过本实验加深对贪心算法、动态规划算法的理解。 二、实验内容: 掌握贪心算法、动态规划算法的概念和基本思想,分析并掌握“0-1”背包问题的求解方法,并分析其优缺点。 三、实验题 1.“0-1”背包问题的贪心算法 2.“0-1”背包问题的动态规划算法 说明:背包实例采用教材P132习题六的6-1中的描述。要求每种的算法都给出最大收益和最优解。 设有背包问题实例n=7,M=15,,(w0,w1,。。。w6)=(2,3,5,7,1,4,1),物品装入背包的收益为:(p0,p1,。。。,p6)=(10,5,15,7,6,18,3)。求这一实例的最优解和最大收益。 四、实验步骤 理解算法思想和问题要求; 编程实现题目要求; 上机输入和调试自己所编的程序; 验证分析实验结果; 整理出实验报告。 五、实验程序

// 贪心法求解 #include #include"iomanip" using namespace std; //按照单位物品收益排序,传入参数单位物品收益,物品收益和物品重量的数组,运用冒泡排序 void AvgBenefitsSort(float *arry_avgp,float *arry_p,float *arry_w ); //获取最优解方法,传入参数为物品收益数组,物品重量数组,最后装载物品最优解的数组和还可以装载物品的重量 float GetBestBenifit(float*arry_p,float*arry_w,float*arry_x,float u); int main(){ float w[7]={2,3,5,7,1,4,1}; //物品重量数组 float p[7]={10,5,15,7,6,18,3}; //物品收益数组 float avgp[7]={0}; //单位毒品的收益数组 float x[7]={0}; //最后装载物品的最优解数组 const float M=15; //背包所能的载重 float ben=0; //最后的收益 AvgBenefitsSort(avgp,p,w); ben=GetBestBenifit(p,w,x,M); cout<

贪心算法实现背包问题算法设计与分析实验报告

算法设计与分析实验报告 实验名称贪心算法实现背包问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1. 优化问题 有n个输入,而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成,而把满足约束条件的子集称为该问题的可行解。可行解一般来说是不唯一的。那些使目标函数取极值(极大或极小)的可行解,称为最优解。 2.贪心法求优化问题 算法思想:在贪心算法中采用逐步构造最优解的方法。在每个阶段,都作出一个看上去最优的决策(在一定的标准下)。决策一旦作出,就不可再更改。作出贪心决策的依据称为贪心准则(greedy criterion)。 3.一般方法 1)根据题意,选取一种量度标准。 2)按这种量度标准对这n个输入排序 3)依次选择输入量加入部分解中。如果当前这个输入量的加入,不满足约束条件,则不把此输入加到这部分解中。 procedure GREEDY(A,n) /*贪心法一般控制流程*/ //A(1:n)包含n个输入// solutions←φ //将解向量solution初始化为空/ for i←1 to n do x←SELECT(A) if FEASIBLE(solution,x) then solutions←UNION(solution,x) endif repeat return(solution) end GREEDY 4. 实现典型的贪心算法的编程与上机实验,验证算法的时间复杂性函数。 二.实验内容 1. 编程实现背包问题贪心算法。通过具体算法理解如何通过局部最优实现全局最优,

并验证算法的时间复杂性。 2.输入5个的图的邻接矩阵,程序加入统计prim算法访问图的节点数和边数的语句。 3.将统计数与复杂性函数所计算比较次数比较,用表格列出比较结果,给出文字分析。 三.程序算法 1.背包问题的贪心算法 procedure KNAPSACK(P,W,M,X,n) //P(1:n)和W(1;n)分别含有按 P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值 和重量。M是背包的容量大小,而x(1:n)是解向量 real P(1:n),W(1:n),X(1:n),M,cu; integer i,n; X←0 //将解向量初始化为零 cu←M //cu是背包剩余容量 for i←1 to n do if W(i)>cu then exit endif X(i) ←1 cu←cu-W(i) repeat if i≤n then X(i) ←cu/ W(i) endif end GREEDY-KNAPSACK procedure prim(G,) status←“unseen” // T为空 status[1]←“tree node” // 将1放入T for each edge(1,w) do status[w]←“fringe” // 找到T的邻接点 dad[w] ←1; //w通过1与T建立联系 dist[w] ←weight(1,w) //w到T的距离 repeat while status[t]≠“tree node” do pick a fringe u with min dist[w] // 选取到T最近的节点 status[u]←“tree node” for each edge(u,w) do 修改w和T的关系 repeat repeat 2.Prim算法

实验项目三 用蛮力法、动态规划法和贪心法求解背包问题

实验项目三 用蛮力法、动态规划法和贪心法求解0/1 背包问题 实验目的 1、学会背包的数据结构的设计,针对不同的问题涉及到的对象的数据结构的设计也不同; 2、对0-1背包问题的算法设计策略对比与分析。 实验内容: 0/1背包问题是给定n 个重量为{w 1, w 2, … ,wn }、价值为{v 1, v 2, … ,vn }的物品和一个容量为C 的背包,求这些物品中的一个最有价值的子集,并且要能够装到背包中。 在0/1背包问题中,物品i 或者被装入背包,或者不被装入背包,设xi 表示物品i 装入背包的情况,则当xi =0时,表示物品i 没有被装入背包,xi =1时,表示物品i 被装入背包。根据问题的要求,有如下约束条件和目标函数: 于是,问题归结为寻找一个满足约束条件式1,并使目标函数式2达到最大的解向量X =(x 1, x 2, …, xn )。 背包的数据结构的设计: typedef struct object { int n;//物品的编号 int w;//物品的重量 int v;//物品的价值 }wup; wup wp[N];//物品的数组,N 为物品的个数 int c;//背包的总重量 1、蛮力法 蛮力法是一种简单直接的解决问题的方法,常常直接基于问题的描述和所涉及的概念定义。蛮力法的关键是依次处理所有的元素。 用蛮力法解决0/1背包问题,需要考虑给定n 个物品集合的所有子集,找出所有可能的子集(总重量不超过背包容量的子集),计算每个子集的总价值,然后在他们中找到价值最大的子集。 所以蛮力法解0/1背包问题的关键是如何求n 个物品集合的所有子集,n 个物品的子集有2的n 次方个,用一个2的n 次方行n 列的数组保存生成的子集,以下是生成子集的算法: ?????≤≤∈≤∑=)1(}1,0{1n i x C x w i n i i i (式1) ∑=n i i i x v 1max (式2)

贪心算法实现01背包问题

贪心算法实现01背包问题 算法思想:贪心原则为单位价值最大且重量最小,不超过背包最大承重量为约束条件。也就是说,存在单位重量价值相等的两个包,则选取重量较小的那个背包。 具体实现过程是:首先可以设置一个备份pvu类型的数组,在不破环原数据的情况下,对此备份数组按单位重量价值从大到小的排序。依次设立两个指针i,j(其中i表示当前应该参与最佳pv值的元素指针,j表示符合约束条件的指针(单位重量价值PV最大,重量最小,不超过最大承重量约束) 代码实现如下: #include using namespace std; typedef struct { int v; int w; float pv; }pvu; void sortByPv(pvu [],int ); int zeroneBags(pvu[],int,int,int * ); void print(pvu a[],int n) { for (int i=0;i

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;iC)break;//当物品重量大于背包容量时 else//小于时 { object[i].Num=1;//物品i放入一件 C-=object[i].Weight;//背包容量减小 } } if(i<=n)//当不能放入整个物品时,选取物品一部分放入 object[i].Num=C/object[i].Weight; for(i=0;i0) cout<<"重量为: "<

01背包问题不同算法设计、分析与对比

实验三01背包问题不同算法设计、分析与对比 一.问题描述 给定n种物品和一背包。物品i的重量是w i,其价值为v i,背包的容量为c。 问题:应如何选择装入背包中的物品,使得装入背包中物品的总价值最大。 说明:在选择装入背包的物品时,对每种物品i只有两个选择,装入背包或不装入背包,也不能将物品装入背包多次。 二.实验内容与要求 实验内容: 1.分析该问题适合采用哪些算法求解(包括近似解)。 动态规划、贪心、回溯和分支限界算法。 2.分别给出不同算法求解该问题的思想与算法设计,并进行算法复杂性分析。 动态规划: 递推方程: m(i,j) = max{m(i-1,j),m(i-1,j-wi)+vi} j >= wi; m(i-1,j) j < wi; 时间复杂度为O(n). 贪心法: 算法思想:贪心原则为单位价值最大且重量最小,不超过背包最大承重量为约束条件。也就是说,存在单位重量价值相等的两个包,则选取重量较小的那个背包。但是,贪心法当在只有在解决物品可以分割的背包问题时是正确的。贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。 用贪心法设计算法的特点是一步一步地进行,根据某个优化测度(可能是目标函数,也可能不是目标函数),每一步上都要保证能获得局部最优解。每一步只考虑一个数据,它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中, 直到把所有数据枚举完,或者不能再添加为止。

回溯法: 回溯法:为了避免生成那些不可能产生最佳解的问题状态,要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点,以减少 问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。 对于有n种可选物品的0/1背包问题,其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时,只要其左儿子结点是一个可行结点,搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。 时间复杂度为:O(2n) 空间复杂度为:O(n) 分支限界算法: 首先,要对输入数据进行预处理,将各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中,节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。 算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点,则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点,仅当右儿子结点满足上界约束时才将它加入子集树和活结点优 先队列。当扩展到叶节点时为问题的最优值。 3.设计并实现所设计的算法。 4.对比不同算法求解该问题的优劣。 这动态规划算法和贪心算法是用来分别解决不同类型的背包问题的,当一件背包物品可以分割的时候,使用贪心算法,按物品的单位体积的价值排序,从大到小取即可。当一件背包物品不可分割的时候,(因为不可分割,所以就算按物品的单位体积的价值大的先取也不一定是最优解)此时使用贪心是不对的,应使用动态规划。

用蛮力法、动态规划法和贪心法求解01背包问题

算法设计与分析 项目名称:用蛮力法、动态规划法和贪心法求解0/1背包问题 作者姓名:余武丹 李红波 刘红梅 完成日期:2013年9月20日

目录 第一章:简介(Introduction) 第二章:算法定义(Algorithm Specification) 第三章:测试结果(Testing Results) 第四章:分析和讨论

第一章:简介(Introduction ) 0/1背包问题是给定n 个重量为{w 1, w 2, … ,wn }、价值为{v 1, v 2, … ,vn }的物品和一个容量为C 的背包,求这些物品中的一个最有价值的子集,并且要能够装到背包中。 在0/1背包问题中,物品i 或者被装入背包,或者不被装入背包,设xi 表示物品i 装入背包的情况,则当xi =0时,表示物品i 没有被装入背包,xi =1时,表示物品i 被装入背包。根据问题的要求,有如下约束条件和目标函数: 于是,问题归结为寻找一个满足约束条件式1,并使目标函数式2达到最大的解向量X =(x 1, x 2, …, xn )。 背包的数据结构的设计: typedef struct object { int n;//物品的编号 int w;//物品的重量 int v;//物品的价值 }wup; wup wp[N];//物品的数组,N 为物品的个数 int c;//背包的总重量 第二章:算法定义(Algorithm Specification ) 1、蛮力法 蛮力法是一种简单直接的解决问题的方法,常常直接基于问题的描述和所涉及的概念定义。蛮力法的关键是依次处理所有的元素。 用蛮力法解决0/1背包问题,需要考虑给定n 个物品集合的所有子集,找出所有可能的子集(总重量不超过背包容量的子集),计算每个子集的总价值,然后在他们中找到价值最大的子集。 所以蛮力法解0/1背包问题的关键是如何求n 个物品集合的所有子集,n 个物品的子集有2的n 次方个,用一个2的n 次方行n 列的数组保存生成的子集,以下是生成子集的算法: void force(int a[][4])//蛮力法产生4个物品的子集 { int i,j; int n=16; int m,t; for(i=0;i<16;i++) ????? ≤≤∈≤∑=) 1(}1,0{1 n i x C x w i n i i i (式1) ∑=n i i i x v 1 max (式2)

相关文档