当前位置：文档之家 › 01背包问题改进算法

01背包问题改进算法

  • 格式：pdf
  • 大小：201.42 KB
  • 文档页数：6

0/1背包问题改进算法

改进算法的求解步骤： ① 初始[1]{(0,0)}pn；

② [1][1](,)iiqipiwv；

③ [][1][1]pipiqi ——其中的受控点；

④ 重复②③，直到计算出[1]p；

⑤ 由[1]p的最后一个跳跃点即为所求问题的最优值(1,)mc。

capacity value next p[1]

p[2]

p[3]

p[4]

p[5]

p[6]

int knapsack( int n, int c, int v[], int w[],pointer p[], int x[] )

{ p[1]=(pointer)malloc(sizeof(struct node));

p[1]capacity=-1;

p[1]value=-1;

p[1]next=null;

for( i=2; i<=n+1; i+= )

{ p[i]=(pointer)malloc(sizeof(struct node));

p[i]capacity=-1;

p[i]value=-1;

p[i]next=null; -1

-1

-1

-1

-1

-1 4 6  0 0

q[i]=(pointer)malloc(sizeof(struct node));

q[i]capacity=-1;

q[i]value=-1;

q[i]next=null;

}

s=(pointer)malloc(sizeof(struct node));

scapacity=0;

svalue=0;

snext=null;

p[n+1]next=s; //初始化p[n+1]={（0,0）}

//输出p[n+1]的信息 cout<

rp=p[n+1] next;

while( rp!=null ) { cout<<”(”<

rp=rpnext;

}

for( i=n; i>=1; i-- )

{ lp=p[i+1] next;

rq=q[i+1];

while( lp!=null )

{ if(lpcapacity+w[i]<=c)

{ s=(pointer)malloc(sizeof(struct node));

scapacity=lpcapacity+w[i];

svalue=lpvalue+v[i];

rqnext=s;

rq=s;

}

lp=lpnext;

}

rqnext=null;

//输出q[i+1]的信息 cout<

rq=q[i+1] next;

while( rq!=null ) { cout<<”(”<

rq=rqnext;

}

lp=p[i+1] next;

lq=q[i+1] next;

rp=p[i];

while( lp!=null&&lq!=null )

{ s=(pointer)malloc(sizeof(struct node));

if( lpcapacity

{ if( lpvalue>rpvalue ) //同时去除受控点

{ scapacity=lpcapacity;

svalue=lpvalue;

rpnext=s;

rp= rpnext;

}

lp=lpnext;

}

else if(lqcapacity

{ if( lqvalue>rpvalue ) //去除受控点

{ scapacity=lqcapacity;

svalue=lqvalue;

rpnext=s;

rp= rpnext;

}

lq=lqnext;

}

else //证明lpcapacity==lqcapacity

{ if( lpvalue>lqvalue ) //包容量相等 选价值大的

{ if( lpvalue>rpvalue ) //去除受控点

{ scapacity=lpcapacity;

svalue=lpvalue;

rpnext=s;

rp= rpnext;

}

lp=lpnext;

}

else

{ if( lqvalue>rpvalue ) //去除受控点

{ scapacity=lqcapacity;

svalue=lqvalue;

rpnext=s;

rp= rpnext;

}

lq=lqnext;

}

}

}

while( lp!=null )

{ s=()malloc();

if( lpvalue>rpvalue )

{ scapacity=lpcapacity;

svalue=lpvalue;

rpnext=s;

rp= rpnext;

}

lp=lpnext;

}

while( lq!=null )

{ s=()malloc();

if( lqvalue>rpvalue )

{ scapacity=lqcapacity;

svalue=lqvalue;

rpnext=s;

rp= rpnext;

}

lq=lqnext;

}

rpnext=null;

//在p[1]中求出最优解，最优值的最后一个结点capacity和value的值

pre=p[1] next;

rp=prenext;

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

{ x[i]=0;tag=1; rp=prenext;

while( rp!=null&&tag==1 )

if( precapacity+w[i]==rpcapacity&&prevalue+v[i]==rpvalue )

{ x[i]=1;

pre=rp;rp=rpnext;tag=0;

}

else rp=rpnext;

}

}

合集下载

遗传算法在0-1一维背包问题上的应用研究

遗传算法在0-1一维背包问题上的应用研究

第３５卷（２ｏｏ７）第１０期　计算机与数字工程　３５　

遗传算法在０—１一维背包问题上的应用研究　

陆鹏高茂庭李迎新　

（上海海事大学信息工程学院上海２００１３５）　

摘要遗传算法是改进式启发算法，模拟自然界生物进化过程的计算模型。本文将多种改进的遗传算法应用于背　

包问题，并通过算例来证明该算法解决背包问题的可行性与有效性，以及评价各算法得优缺点。　

关键词遗传算法背包问题交叉算子变异算子二重结构编码　’　

中图分类号ＴＰ３９１．９　

１　引言　

众所周知背包问题（ｋｎａｐｓａｃｋ　ｐｒｏｂｌｅｍ）是典型　

的ＮＰ完全问题。它数学模型是一个０—１规划问　

题，表示如下：　

ｆＭａｘ　∑ｎ．＿ｌＣｉＸｉ　

【ｓ．ｔ．　∑ｎ．＿１ａｉＸｉ≤ｂ（Ｘｉ＝１或０）　

半个世纪以来，该问题一直是算法与复杂性研　

究的热点问题之一。而遗传算法是改进式启发算　

法，利用了生物学的概念先建立一组可行解的种　

群，并加以编码，然后通过遗传，交叉和变异对现有　

种群进行迭代以求的问题最优解。它适用于大规　

模，多峰多态函数，含离散变量等情况下的全局最　

优化问题。故本文将遗传算法应用于解决背包问　

题，并通过算例来证明算法的可行性与有效性。　即将超过约束条件的个体直接摈弃。从实验　

结果上看这是可行的。　

４　选择　

采用轮盘赌选择方法。另外为了算法的收敛　

性，引入最优值保持策略：让每次迭代产生的新种　

群中适应度最优个体与父个体中适应度最优的相　

比较，如果比后者大，则不论。否则讲父个体中适　

应度最优个体替代新种群中适应度最差的个体。　

５　交叉算子　

采用单点杂交算子，在两个父代染色体的编码　

串上随机选择一个杂交位，在此位后的两部分进行　

交换，产生新的子代染色体。交叉概率一般设为　

０．８左右。　

２　遗传算法编码　６　变异算子　

对于遗传算法来说首先要解决的是其编码问　

题。正因为背包问题属于０—１规划问题，所以我　

们直接采用二进制编码。例如一个８变量的背包　

问题：当产生一个二进制的编码个体（１００１０１０１）　

贪心算法-01背包问题

贪心算法-01背包问题

贪⼼算法-01背包问题

1、问题描述：

给定n种物品和⼀背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装⼊背包的物品，使得装⼊背包中物品的总价值

最⼤?

形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找⼀n元向量(x1,x2,…,xn,), xi∈{0,1}, ∋ ∑ wi xi≤c,且∑ vi xi达最⼤.即⼀个特殊的整数规划

问题。

2、最优性原理：

设(y1,y2,…,yn)是 (3.4.1)的⼀个最优解.则(y2,…,yn)是下⾯相应⼦问题的⼀个最优解:

证明:使⽤反证法。若不然,设(z2,z3,…,zn)是上述⼦问题的⼀个最优解,⽽(y2,y3,…,yn)不是它的最优解。显然有

∑vizi > ∑viyi (i=2,…,n)

且 w1y1+ ∑wizi<= c

因此 v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n)

说明(y1,z2, z3,…,zn)是(3.4.1)0-1背包问题的⼀个更优解,导出(y1,y2,…,yn)不是背包问题的最优解,⽭盾。

3、递推关系：

设所给0-1背包问题的⼦问题

的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优⼦结构性质，

可以建⽴计算m(i，j)的递归式:

注:(3.4.3)式此时背包容量为j，可选择物品为i。此时在对xi作出决策之后,问题处于两种状态之⼀:

(1)背包剩余容量是j,没产⽣任何效益；

(2)剩余容量j-wi,效益值增长了vi ；

使⽤递归C++代码如下：

#include

using namespace std;

const int N=3;

const int W=50;

int weights[N+1]={0,10,20,30};

int values[N+1]={0,60,100,120};

求解多维0-1背包问题的一种改进的遗传算法

求解多维0-1背包问题的一种改进的遗传算法

计算机科学２００６Ｖｏ１．３３Ｎｏ．７　

求解多维０—１背包问题的一种改进的遗传算法　）　

曾智杨小帆陈静陈文斌唐荣旺　

（重庆大学计算机学院　重庆４０００４４）　

摘要针对多维Ｏ一１背包问题，通过应用贪心法和二分搜索法的思想，本文提出了一种新的杂交算子——中值杂　

交，并且基于此算子提出了求解多维Ｏ一１背包问题的一种改进的遗传算法。最后本文通过一系列数值实验，把改进算　

法与传统的遗传算法以及其他最新的遗传算法进行比较，经过对求得近似解的精度及计算所需时间两方面的对比，验　

证了其有效性。　

关键词　多维Ｏ一１背包问题，遗传算法，中值杂交算子　

Ａｎ　Ｉｍｐｒｏｖｅｄ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｈｅ　Ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ　０—１　Ｋｎａｐｓａｃｋ　Ｐｒｏｂｌｅｍ　

ＺＥＮＧＺｈｉ　ＹＡＮＧＸｉａｏ－Ｆａｎ　ＣＨＥＮ　Ｊｉｎｇ　ＣＨＥＮＷｅｎ－Ｂｉｎ　ＴＡＮＧＲｏｎｇ－Ｗａｎｇ　

（Ｃｏｍｐｕｔｅｒ　Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｈｏｎｇｑｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｏｎｇｑｉｎｇ　４０００４４）　

Ａｂｓｔｒａｃｔ　Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａ　ｎｅｗ　ｃｒｏｓｓｏｖｅｒ　ｏｐｅｒａｔｏｒ　ｗｈｉｃｈ　ｉｓ　ｃａｌｌｅｄ　ｍｅｄｉａｎ　ｃｒｏｓｓｏｖｅｒ．Ｉｔ　ｉｓ　ｄｅｓｉｇｎｅｄ　ｂｙ　ｕｓｉｎｇ　ｔｈｅ　ｉ—　

ｄｅａｓ　ｏｆ　ｔｈｅ　ｇｒｅｅｄｙ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｔｈｅ　２一ｄｉｖｉｓｉｏｎ　ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍ，ａｎｄ　ａｉｍｓ　ａｔ　ｔｈｅ　ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ　０－１　ｋｎａｐｓａｃｋ　ｐｒｏｂ—　

ｌｅｍ．Ｂａｓｅｄ　ｏｎ　ｔｈｉｓ　ｍｅｄｉａｎ　ｃｒｏｓｓｏｖｅｒ　ｏｐｅｒａｔｏｒ，ｔｈｅ　ｐａｐｅｒ　ａｌｓｏ　ｐｒｅｓｅｎｔｓ　ａｎ　ｉｍｐｒｏｖｅｄ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｓｏｌｖｉｎｇ　ｔｈｅ　

ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ　０－１　ｋｎａｐｓａｃｋ　ｐｒｏｂｌｅｍ．Ｆｕｒｔｈｅｒｍｏｒｅ，ｔｈｅ　ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ｔｈｅ　ｐｒｅｓｅｎｔｅｄ　ｍｅｔｈｏｄ　ｉｓ　ｉｎｖｅｓｔｉｇａｔｅｄ　ｂｙ　ｃｏｍｐａ—　

浅谈0-1背包问题的常用算法

浅谈0-1背包问题的常用算法

２０１３年１０月下　消费电子　

Ｃｏｎｓｕｍｅｒ　Ｅｌｅｃｔｒｏｎｉｃｓ　Ｍａｇａｚｉｎｅ　技术交流　

浅谈０－１背包问题的常用算法　

汤赫男　

（吉林工商学院信息工程学院，长春１３００６２）　

摘要：０－１背包问题是典型的ＮＰ～完全问题，无论从理论上还是实践上都有一定的研究意义。本文综述了几　

种０—１背包问题的常用算法，分析算法的优劣，预测０－１背包问题的发展方向。　

关键词：０—１背包问题；动态规划法；贪心法；分支界限法　

中图分类号：ＴＰ１８　文献标识码：Ａ　文章编号：１６７４＝７７１２（２０１３）２０—０２１５—０１　

０－１背包问题是背包问题的一个特例，二者的区别在于　

物品装入背包过程中是否可以部分装入；可以部分装入的属　

于背包问题研究范畴，不可以部分装入的背包问题可以描述　

为０－１背包问题。０－１背包问题的应用广泛，许多的实际问题　

都可以转化为０－１背包问题。例如：贷款组合优化决策问题、　

项目投资问题、预算控制、货物装载等。所以，Ｏ—ｌ背包问题　

的算法研究无论是在理论上还是在实践中都具有深远的意义。　

一、０－１背包问题的抽象模型描述　

（一）０－１背包问题描述。给定ｎ个物品，这ｎ个物品　

的重量分别为｛ｗ１，ｗ２，…，ｗｎ｝，这ｎ个物品的价值分别　

为｛ｖ１，ｖ２，…，ｖｎ），有～个容量为Ｃ的背包，如何选择　

装入背包的物品，使得装入背包中物品的总价值最大，对于　

每种物品只有两种选择：装入背包或不装入背包。　

（二）抽象模型描述　

∑ｗ　，　㈠｛　“｝　ｍａｘ∑　

｛　ｌ　ｊ　｛　二、常用的０－１背包问题算法　

（一）蛮力法。蛮力法又称穷举法或枚举法，是一种简单、　

直接、有效的方法，是初学者入门的方法。蛮力法要求遍历所　

有可能情况一次且仅一次，筛选出符合要求的解。应用蛮力法　

求解０－１背包问题，需要考虑给定的ｎ个物品集合的所有子集，　

找出所有总重量不超过背包容量的子集，计算每个可能子集的　

总价值，然后找出价值最大的子集。对于一个具有ｎ个元素的