搜档网
当前位置:搜档网 › 用蛮力法、动态规划法和贪心法求解0 1背包问题

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

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

实验项目三 用蛮力法、动态规划法和贪心法求解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)

void force(int a[][4])//蛮力法产生4个物品的子集

{

int i,j;

int n=16;

int m,t;

for(i=0;i<16;i++)

{ t=i;

for(j=3;j>=0;j--)

{

m=t%2;

a[i][j]=m;

t=t/2;

}

}

for(i=0;i<16;i++)//输出保存子集的二维数组

{

for(j=0;j<4;j++)

{

printf("%d ",a[i][j]);

}

printf("\n");

}

以下要依次判断每个子集的可行性,找出可行解:

void panduan(int a[][4],int cw[])////判断每个子集的可行性,如果可行则计算其价值存入数组cw,不可行则存入0

{

int i,j;

int n=16;

int sw,sv;

for(i=0;i<16;i++)

{

sw=0;

sv=0;

for(j=0;j<4;j++)

{

sw=sw+wp[j].w*a[i][j];

sv=sv+wp[j].v*a[i][j];

}

if(sw<=c)

cw[i]=sv;

else

cw[i]=0;

}

在可行解中找出最优解,即找出可行解中满足目标函数的最优解。以下是找出最优解的算法:

int findmax(int x[16][4],int cv[])//可行解保存在数组cv中,最优解就是x数组中某行的元素值相加得到的最大值

{

int max;

int i,j;

max=0;

for(i=0;i<16;i++)

{

if(cv[i]>max)

{max=cv[i];

j=i;

}

}

printf("\n最好的组合方案是:");

for(i=0;i<4;i++)

{

printf("%d ",x[j][i]);

}

return max;

}

2、动态规划法

动态规划法将待求解问题分解成若干个相互重叠的子问题,每个子问题对应决策过程的一个阶段,一般来说,子问题的重叠关系表现在对给定问题求解的递推关系(也就是动态规划函数)中,将子问题的解求解一次并填入表中,当需要再次求解此子问题时,可以通过查表获得该子问题的解而不用再次求解,从而避免了大量重复计算。

动态规划法设计算法一般分成三个阶段:

(1)分段:将原问题分解为若干个相互重叠的子问题;

(2)分析:分析问题是否满足最优性原理,找出动态规划函数的递推式;

(3)求解:利用递推式自底向上计算,实现动态规划过程。

0/1背包问题可以看作是决策一个序列(x1, x2, …, xn),对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策后,已确定了(x1, …, xi-1),在决策xi时,问题处于下列两种状态之一:

(1)背包容量不足以装入物品i,则xi=0,背包不增加价值;

(2)背包容量可以装入物品i,则xi=1,背包的价值增加了vi。

这两种情况下背包价值的最大者应该是对xi决策后的背包价值。令V(i, j)表示在前i(1≤i≤n)个物品中能够装入容量为j(1≤j≤C)的背包中的物品的最大值,则可以得到如下动态规划函数:

V (i , 0)= V (0, j )=0 (式3)

(式4)

式3表明:把前面i 个物品装入容量为0的背包和把0个物品装入容量为j 的背包,得到的价值均为0。式4的第一个式子表明:如果第i 个物品的重量大于背包的容量,则装入前i 个物品得到的最大价值和装入前i -1个物品得到的最大价值是相同的,即物品i 不能装入背包;第二个式子表明:如果第i 个物品的重量小于背包的容量,则会有以下两种情况:

(1)如果把第i 个物品装入背包,则背包中物品的价值等于把前i -1个物品装入容量为j -wi 的背包中的价值加上第i 个物品的价值vi ;(2)如果第i 个物品没有装入背包,则背包中物品的价值就等于把前i -1个物品装入容量为j 的背包中所取得的价值。显然,取二者中价值较大者作为把前i 个物品装入容量为j 的背包中的最优解。

以下是动态规划法求解背包问题的算法:

int findmaxvalue(wup *p,int x[])//x 数组用来存放可行解,p 是指向存放物品数组的指针 {

int i,j;

int maxvalue;

int value[N+1][C+1];

for(j=0;j<=C;j++)

value[0][j]=0; //初始化第0行

for(i=0;i<=N;i++)

value[i][0]=0;//初始化第0列

//计算数组value 中各元素的值

for(i=1;i<=N;i++,p++)

for(j=1;j<=C;j++)

{

if(p->w >j)

{

value[i][j]=value[i-1][j];

}

else

{

value[i][j]=max(value[i-1][j],(value[i-1][j-p->w]+p->v));//max 函数求两个数当中的大者

}

}

//逆推求解

j=C;

for(i=N;i>0;i--)

{

if(value[i][j]>value[i-1][j])

{

???>+---<-=i i i i w j v w j i V j i V w j j i V j i V }),1(),,1(max{),1(),(

x[i-1]=1;//是否被选中的向量的下标也是从0开始

j=j-wp[i-1].w;//存放物品的下标从0开始

}

else

x[i-1]=0;

}

maxvalue=value[N][C];//最大值

return maxvalue;

}

3、贪心法

贪心法在解决问题的策略上目光短浅,只根据当前已有的信息就做出选择,而且一旦做出了选择,不管将来有什么结果,这个选择都不会改变。换言之,贪心法并不是从整体最优考虑,它所做出的选择只是在某种意义上的局部最优。

这种局部最优选择并不总能获得整体最优解(Optimal Solution),但通常能获得近似最优解(Near-Optimal Solution)。

贪心法求解的问题的特征:

(1)最优子结构性质

当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质,也称此问题满足最优性原理。

(2)贪心选择性质

所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来得到。

用贪心法求解问题应该考虑如下几个方面:

(1)候选集合C:为了构造问题的解决方案,有一个候选集合C作为问题的可能解,即问题的最终解均取自于候选集合C。例如,在付款问题中,各种面值的货币构成候选集合。

(2)解集合S:随着贪心选择的进行,解集合S不断扩展,直到构成一个满足问题的完整解。例如,在付款问题中,已付出的货币构成解集合。

(3)解决函数solution:检查解集合S是否构成问题的完整解。例如,在付款问题中,解决函数是已付出的货币金额恰好等于应付款。

(4)选择函数select:即贪心策略,这是贪心法的关键,它指出哪个候选对象最有希望构成问题的解,选择函数通常和目标函数有关。例如,在付款问题中,贪心策略就是在候选集合中选择面值最大的货币。

(5)可行函数feasible:检查解集合中加入一个候选对象是否可行,即解集合扩展后是否满足约束条件。例如,在付款问题中,可行函数是每一步选择的货币和已付出的货币相加不超过应付款。

背包问题至少有三种看似合理的贪心策略:

(1)选择价值最大的物品,因为这可以尽可能快地增加背包的总价值。但是,虽然每一步选择获得了背包价值的极大增长,但背包容量却可能消耗得太快,使得装入背包的物品个数减少,从而不能保证目标函数达到最大。

(2)选择重量最轻的物品,因为这可以装入尽可能多的物品,从而增加背包的总价值。但是,虽然每一步选择使背包的容量消耗得慢了,但背包的价值却没能保证迅速增长,

从而不能保证目标函数达到最大。

(3)选择单位重量价值最大的物品,在背包价值增长和背包容量消耗两者之间寻找平衡。

应用第三种贪心策略,每次从物品集合中选择单位重量价值最大的物品,如果其重量小于背包容量,就可以把它装入,并将背包容量减去该物品的重量,然后我们就面临了一个最优子问题——它同样是背包问题,只不过背包容量减少了,物品集合减少了。因此背包问题具有最优子结构性质。

先按单位重量价值最大对物品进行排序。

然后再用贪心策略选择的算法如下:

float find(float p[N],float w[N],float x[N] ,float M,int n) /*先放单位价值量大的物体,再考虑小的物体*/

{

int i;

float maxprice;

for (i = 0; i < n; i++)

x[i] = 0;

i = 0;

maxprice=0;

while (i < n && w[i] < M)

{

M=M-w[i];

x[i] =w[i]; /* 表示放入数量*/

maxprice=maxprice+p[i];

x[n-1]=M;

i++;

}

if (i < n &&M> 0)

{

maxprice=maxprice+p[i]*x[i]/w[i];

i++;

}

return maxprice;

}

#include

#include

#include

#define C 10//定义背包总重量为10

#define N 4//定义物品个数为4

typedef struct object//背包的数据结构的设计

{

int n;//物品的编号

int w;//物品的重量

int v;//物品的价值

}wup;

wup wp[N];//物品的数组,N为物品的个数

void inputwp(wup *p)//输入函数

{

int i;//i为物品的个数

for (i=0;i

{

printf("\n请输入第%d个物品的编号、重量、价值",i);

scanf("%d",&p->n);//输入物品的编号

scanf("%d",&p->w);//输入物品的重量

scanf("%d",&p->v);//输入物品的价值

p=p+1;//p为一个指针,指向下一个物品

}

printf("\n");//输出结果

}

void ontputwp(wup *p)//输出函数

{

int i;//i为物品的个数

for (i=0;i

{

printf("\n请输出第%d个物品的编号、重量、价值",i);

printf("%d %d %d",p->n,p->w,p->v);/*把物品的编号、重量、价值和起来输出给i个物品*/

p=p+1;//指针指向下一个物品

}

printf("\n");//输出结果

}

float find(float y[N],float w[N],float x[N] ,float M,int n) /*先放单位价值量大的物体,再考虑小的物体*/

{

int i;

float maxprice;

for (i = 0; i < n; i++)

x[i] = 0;

i = 0;

maxprice=0;

while (i < n && w[i] < M)

{

M=M-w[i];

x[i] =w[i]; /* 表示放入数量*/

maxprice=maxprice+y[i];

x[n-1]=M;

i++;

}

if (i < n &&M> 0)

{

maxprice=maxprice+y[i]*x[i]/w[i];

i++;

}

return maxprice;

}

void main()

{

wup *p;//这是一个wup型的指针p

float y[N];

float w[N];

float x[N];

float M;

int n;

int i;

float maxprice;

printf("背包的总重量:%d",C);

p=wp;

inputwp(p);//输入物品信息

p=wp;

ontputwp(p);//输出物品信息

maxprice=find(y,w,x,M,n);//找出最大价值并赋给maxprice;

printf("\n最大的价值是:%d\n",maxprice);//输出最大的价值printf("物品最佳的组合:\n");//输出最佳的组合

for(i=0;i

{

printf("%d",x[i]);

}

printf("\n");

}

贪心算法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; } 测试截图为:

动态规划与回溯法解决0-1背包问题

0-1背包动态规划解决问题 一、问题描述: 有n个物品,它们有各自的重量和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和? 二、总体思路: 根据动态规划解题步骤(问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成)找出01背包问题的最优解以及解组成,然后编写代码实现。 原理: 动态规划与分治法类似,都是把大问题拆分成小问题,通过寻找大问题与小问题的递推关系,解决一个个小问题,最终达到解决原问题的效果。但不同的是,分治法在子问题和子子问题等上被重复计算了很多次,而动态规划则具有记忆性,通过填写表把所有已经解决的子问题答案纪录下来,在新问题里需要用到的子问题可以直接提取,避免了重复计算,从而节约了时间,所以在问题满足最优性原理之后,用动态规划解决问题的核心就在于填表,表填写完毕,最优解也就找到。 过程: a) 把背包问题抽象化(X1,X2,…,Xn,其中 Xi 取0或1,表示第i个物品选或不选),V i表示第i个物品的价值,W i表示第i个物品的体积(重量); b) 建立模型,即求max(V1X1+V2X2+…+VnXn); c) 约束条件,W1X1+W2X2+…+WnXn (V2X2+V3X3+…+VnXn)+V1X1;

分治、贪心、动态规划算法要点复习

分治法 1 分割成独立的子问题 2 递归解决子问题 3 合并求得初始问题的解 动态规划算法 1.描述最优解的结构特征 2.定义最优解决方案的递归形式 3.以自底向上的方式计算最优解决方案的值 4.从计算信息构造出最优解决方案 贪婪算法步骤 1.确定问题的优化结构 2.得到递归解 3.证明某个最优选择是贪婪选择 4.贪婪选择将产生唯一一个非空子问题 5.用递归算法实现贪婪策略 6.将递归算法转换为迭代算法 贪婪算法设计 1. 通过作出某种贪婪选择,将初始优化问题转换为唯一的一个子问题来求解 2. GREEDY CHOICE(证明贪婪选择) 作出该贪婪选择后,可以保证初始优化问题存在最优解3.OPTIMAL SUBSTRUCTURE(证明优化基础) 贪婪选择+唯一子问题=最优解 贪婪算法正确性 1. 贪婪选择特性(局部最优导致全局最优) 2. 优化基础的特性(贪婪选择+唯一子问题的最优解?初始问题的最优解) 作业选择 ?贪婪选择特性 存在最优解包含贪婪选择,即Sij在选择最先完成的作业am ?优化基础 If an optimal solution to subproblem Sij includes activity ak ? it must contain optimal solutions to Sik and Skj Solution to Sij=(Solution to Sik)∪{ak}∪(Solution to Skj)动态规划解) Similarly, am + optimal solution to Smj ? optimal sol. Solution to Sij = {am} ∪(Solution to Smj) (贪婪选择解) 动态规划与贪婪算法比较 ?Dynamic programming –每步选择–选择与子问题解相关 –自底向上,即从规模下的子问题逐步求解规模大的子问题?Greedy algorithm –首先作出贪婪选择–求解贪婪选择后产生的唯一子问题–后续贪婪选择与前面的选择有关,但与子问题的解无关 –自顶向下,问题规模逐步缩小 动态规划和分治法 ?子问题非独立 –子问题求解依赖其子问题的解 –分治法通过递归方式解决性质相同的子问题 –动态规划每次解决一个子问题,并将结果存储在表格中4 ?适合优化问题 –通过适当的选择来获得问题的最优解 –找到具有最优解决方案及其最优值:装配线排程方案以及该方案的生产时间 –导致最优的解决方案可能不止一个 ? (允许负权值边) –如果从源顶点s没有可抵达的负权值回路,返回‘真’)(其余的返回‘假’,无解 –遍历所有的边|V–1|次,每次对每条边执行一次缩短运算–对图进行拓扑排序)(依据拓扑排序对边进行缩短操作 于每一个顶点, 对始于该顶点的每条边进行缩短操作) (DGA中没有负权值回路, 因此存在最短路径) – (不存在负权值边界) – (S: 集合中顶点的最短路径已经确定) (Q: V – S, 极小优先队列) ? (d[v]) (Q中的值是最短路径的估计) ?重复的从Q中选择具有最短估计距离的顶点进行处理 The Ford-Fulkerson Method(不断的增大流, 直到达到流的极大值)(通过剩余流和剩余流图实现) 增量算法(An Incremental Algorithm) Alg.: GREEDY-ACTIVITY-SELECTOR(s, f, n) 1. A ← {a1} 2. i ← 1 3. for m ← 2 to n 4. do if sm ≥ fi ? activity am is compatible with ai 5. then A ← A ∪ {am} 6. i ← m ? ai is most recent addition to A 7. return A 动态规划: 装配线排程 e1 + a1,1 if j = 1 f1[j] = min(f1[j - 1] + a1,j ,f2[j -1] + t2,j-1 + a1,j) if j ≥ 2 矩阵链相乘 m[i,j]=0 if i = j min{m[i,k]+m[k+1,j]+pi-1pkpj} if i < j Matrix-Chain-Order(p) 1. n ←length[p]-1; 2. for i ←1 to n 3. m[i, i] ←0; 4. for l ←2 to n 5. for i ←1 to n –l +1 6. j ←i + l -1; 7. m[i, j] ←∞; 8. for k ←i to j -1 9. q ←m[i, k] + m[k+1, j] + pI-1pkpj; 10. if q < m[i, j] 11. m[i, j] ←q; 12. s[i, j] ←k; 13. return m and s 最长共同子序列 LCS-Length(X,Y) 1. m ←length[X]; 2. n ←length[Y]; 3. for i ←1 to m 4. c[i, 0] ←0; 5. for j ←0 to n 6. c[0, j] ←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

动态规划算法原理与的应用

动态规划算法原理及其应用研究 系别:x x x 姓名:x x x 指导教员: x x x 2012年5月20日

摘要:动态规划是解决最优化问题的基本方法,本文介绍了动态规划的基本思想和基本步骤,并通过几个实例的分析,研究了利用动态规划设计算法的具体途径。关键词:动态规划多阶段决策 1.引言 规划问题的最终目的就是确定各决策变量的取值,以使目标函数达到极大或极小。在线性规划和非线性规划中,决策变量都是以集合的形式被一次性处理的;然而,有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程:它可以分解为若干个互相联系的阶段,在每一阶段分别对应着一组可供选取的决策集合;即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列,称为一个策略。显然,由于各个阶段选取的决策不同,对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时,相应可以得到一个确定的效果,采取不同的策略,就会得到不同的效果。多阶段的决策问题,就是要在所有可能采取的策略中选取一个最优的策略,以便得到最佳的效果。动态规划是一种求解多阶段决策问题的系统技术,可以说它横跨整个规划领域(线性规划和非线性规划)。在多阶段决策问题中,有些问题对阶段的划分具有明显的时序性,动态规划的“动态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼(Bellman)。20世纪40年代末50年代初,当时在兰德公司(Rand Corporation)从事研究工作的贝尔曼首先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论文,并出版了他的第一部著作《动态规划》。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。在贝尔曼及其助手们致力于发展和推广这一技术的同时,其他一些学者也对动态规划的发展做出了重大的贡献,其中最值得一提的是爱尔思(Aris)和梅特顿(Mitten)。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作,并于1964年同尼母霍思尔(Nemhauser)、威尔德(Wild)一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点,并且对明晰动态规划路径的数

贪心算法与动态规划的比较

贪心算法与动态规划的比较 【摘要】介绍了计算机算法设计的两种常用算法思想:贪心算法与动态规划算法。通过介绍两种算法思想的基本原理,比较两种算法的联系和区别。通过背包问题对比了两种算法的使用特点和使用范围。 【关键字】动态规划;贪心算法;背包问题 1、引言 为了满足人们对大数据量信息处理的渴望,为解决各种实际问题,计算机算法学得到了飞速的发展,线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中,产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不像是技术,但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法,你可以使用这些方法来设计算法,并观察这些算法是如何工作的。一般情况下,为了获得较好的性能,必须对算法进行细致的调整。但是在某些情况下,算法经过调整之后性能仍无法达到要求,这时就必须寻求另外的方法来求解该问题。本文针对部分背包问题和0/ 1 背包问题进行分析,介绍贪心算法和动态规划算法的区别。 2、背包问题的提出 给定n种物品( 每种物品仅有一件) 和一个背包。物品i的重量是w i,其价值为p i,背包的容量为M。问应如何选择物品装入背包,使得装入背包中的物品的总价值最大,每件物品i的装入情况为x i,得到的效益是p i*x i。 ⑴部分背包问题。在选择物品时,可以将物品分割为部分装入背包,即0≤x i≤1 ( 贪心算法)。 ⑵0/ 1背包问题。和部分背包问题相似,但是在选择物品装入时要么不装,要么全装入,即x i = 1或0。( 动态规划算法) 。 3、贪心算法 3.1 贪心算法的基本要素 能够使用贪心算法的许多例子都是最优化问题,每个最优化问题都包含一组限制条件和一个优化函数,符合限制条件的问题求解方案称为可行解;使优化函数取得最佳值的可行解称为最优解。此类所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到(这是贪心算法与动态规划的主要区别) 。 3.2贪心策略的定义 贪心策略是指从问题的初始状态出发,通过若干次的贪心选择而得出最优值( 或较优解) 的一种解题方法。贪心策略总是做出在当前看来是最优的选择,也就是说贪心策略并不是从整体上加以考虑,它所做出的选择只是在某种意义上的局部最优解,而许多问题自身的特性决定了该问题运用贪心策略可以得到最优解或较优解。(注:贪心算法不是对所有问题都能

【精选】贪心算法的应用

贪心算法的应用 课程名称:算法设计与分析 院系:计算机科学与信息工程学院 学生姓名:**** 学号:********** 专业班级:********************************** 指导教师:****** 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)

经典算法——动态规划教程

动态规划是对最优化问题的一种新的算法设计方法。由于各种问题的性质不同,确定最优解的条件也互不相同,因而动态规划的没计法对不同的问题,有各具特色的表示方式。不存在一种万能的动态规划算法。但是可以通过对若干有代表性的问题的动态规划算法进行讨论,学会这一设计方法。 多阶段决策过程最优化问题 ——动态规划的基本模型 在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定,它依赖于当前面临的状态,又影响以后的发展。当各个阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线。这种把一个问题看做是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,这种问题称为多阶段决策最优化问题。 【例题1】最短路径问题。图中给出了一个地图,地图中每个顶点代表一个城市,两个城市间的连线代表道路,连线上的数值代表道路的长度。现在,想从城市A到达城市E,怎样走路程最短,最短路程的长度是多少? 【分析】把从A到E的全过程分成四个阶段,用k表示阶段变量,第1阶段有一个初始状态A,两条可供选择的支路ABl、AB2;第2阶段有两个初始状态B1、 B2,B1有三条可供选择的支路,B2有两条可供选择的支路……。用dk(x k,x k+1)表示在第k阶段由初始状态x k到下阶段的初始状态x k+1的路径距离,Fk(x k)表示从第k阶段的x k到终点E的最短距离,利用倒推方法求解A到E的最短距离。具体计算过程如下: S1:K=4,有:F4(D1)=3,F4(D2)=4,F4(D3)=3 S2: K=3,有: F3(C1)=min{d3(C1,D1)+F4(D1),d3(C1,D2)+F4(d2)}=min{8,10}=8 F3(C2)=d3(C2,D1)+f4(D1)=5+3=8 F3(C3)=d3(C3,D3)+f4(D3)=8+3=11 F3(C4)=d3(C4,D3)+f4(D3)=3+3=6

01背包问题动态规划详解

动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些结果减轻运算量。 比如01背包问题。 因为背包最大容量M未知。所以,我们的程序要从1到M一个一个的试。比如,开始任选N件物品的一个。看对应M的背包,能不能放进去,如果能放进去,并且还有多的空间,则,多出来的空间里能放N-1物品中的最大价值。怎么能保证总选择是最大价值呢?看下表。 测试数据: 10,3 3,4 4,5 5,6 c[i][j]数组保存了1,2,3号物品依次选择后的最大价值. 这个最大价值是怎么得来的呢?从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为 4,5,6,....10的时候,最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候,最佳方案还是上一排的最价方案c为4.而背包容量为5的时候,则最佳方案为自己的重量5.背包容量为7的时候,很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排c3的最佳方案是4.所以。 总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.) 从以上最大价值的构造过程中可以看出。 f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程.这回清楚了吗?

下面是实际程序: #include int c[10][100]; int knapsack(int m,int n) { int i,j,w[10],p[10]; for(i=1;ic[i-1][j]) c[i][j]=p[i]+c[i-1][j-w[i]]; else c[i][j]=c[i-1][j]; }

背包问题(贪心算法)

算法分析与设计实验报告 第 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

动态规划之01背包问题(最易理解的讲解)

01背包问题,是用来介绍动态规划算法最经典的例子,网上关于01背包问题的讲解也很多,我写这篇文章力争做到用最简单的方式,最少的公式把01背包问题讲解透彻。 01背包的状态转换方程f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] } f[i,j]表示在前i件物品中选择若干件放在承重为j 的背包中,可以取得的最大价值。 Pi表示第i件物品的价值。 决策:为了背包中物品总价值最大化,第i件物品应该放入背包中吗? 题目描述: 有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为10的背包,如何让背包里装入的物品具有最 首先要明确这张表是从右到左,至底向上生成的。 为了叙述方便,用e10单元格表示e行10列的单元格,这个单元格的意义是用来表示只有物品e时,有个承重为10的背包,那么这个背包的最大价值是6,因为e物品的重量是4,背包装的了,把e装进去后价值为6。然后是e9单元格表示背包承重9,只有物品e, e装进去后,背包价值为6,接着是e8, e7单元格,一直到e3单元格表示背包承重3,但物品e承重4,装不了,所以e3=0, 对于d10单元格,表示只有物品e,d时,承重为10的背包,所能装入的最大价值,是10,因为物品e,d这个背包都能装进去。对于承重为9的背包,d9=10,是怎么得出的呢? 根据01背包的状态转换方程,需要考察两个值, 一个是f[i-1,j],对于这个例子来说就是e9的值6,另一个是f[i-1,j-Wi]+Pi; 在这里, f[i-1,j]表示我有一个承重为9的背包,当只有物品e可选时,这个背包能装入的最大价值 f[i-1,j-Wi]表示我有一个承重为4的背包(等于当前背包承重减去物品d的重量),当只有物品e可选时,这个背包能装入的最大价值 f[i-1,j-Wi]就是指单元格e4值为6,Pi指的是d物品的价值,即4 由于f[i-1,j-Wi]+Pi = 6 + 4 = 10 大于f[i-1,j] = 6,所以物品d应该放入承重为9的背包,所以d9=10.

动态规划算法和贪心算法的比较与分析

动态规划算法和贪心算法的比较与分析 1、最优化原理 根据一类多阶段问题的特点,把多阶段决策问题变换为一系列互相联系的单阶段问题,然后逐个加以解决。解决这类问题的最优化原理:一个过程的最优决策具有这样的性质,即无论其初始状态和初始决策如何,其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言,必须构成最优策略。简而言之,一个最优策略的子策略,对于它的初态和终态而言也必是最优的。 2、动态规划 2.1 动态规划算法 动态规划是运筹学的一个分支,与其说它是一种算法,不如说它是一种思维方法更贴切。因为动态规划没有固定的框架,即便是应用到同一道题上,也可以建立多种形式的求解算法。许多隐式图上的算法,例如求单源最短路径的Dijkstra算法、广度优先搜索算法,都渗透着动态规划的思想。还有许多数学问题,表面上看起来与动态规划风马牛不相及,但是其求解思想与动态规划是完全一致的。因此,动态规划不像深度或广度优先那样可以提供一套模式,需要的时候,取来就可以使用。它必须对具体问题进行具体分析、处理,需要丰富的想象力去建立模型,需要创造性的思想去求解。 动态规划算法的基本思想是将待求解问题分解成若干子问题,先求解子问题,然后从这些子问题的解得到原问题的解。值得注意的是,用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的。 最优化原理是动态规划的基础。任何一个问题,如果失去了这个最优化原理的支持,就不可能用动态规划方法计算。能采用动态规划求解的问题都要满足两个条件:①问题中的状态必须满足最优化原理;②问题中的状态必须满足无后效性。 所谓无后效性是指下一时刻的状态只与当前状态有关,而和当前状态之前的状态无关,当前的状态是对以往决策的总结。 2.2 动态规划算法的基本要素

贪心算法背包问题

算法设计与分析实验报告 题目:贪心算法背包问题 专业: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”背包问题 一、实验目的与要求 熟悉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<

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页

算法分析与程序设计动态规划及回溯法解背包问题

动态规划法、回溯法解0-1背包问题 2012级计科庞佳奇 一、问题描述与分析 1.动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会 有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。 不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。 多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义,称这种解决多阶段决策最优化问题的方法为动态规划方法。任何思想方法都有一定的局限性,超出了特定条件,它就失去了作用。同样,动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。1.最优化原理(最优子结构性质)最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。2.无后效性将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。3.子问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余,这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其它的算法。 01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2……Wn,与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。 2.回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目 标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。 在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。

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

实验项目三 用蛮力法、动态规划法和贪心法求解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)

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

算法设计与分析实验报告 实验名称贪心算法实现背包问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 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算法

相关主题