解 0—1 规划的隐枚举法

1 关于求解0/1背包问题的动态规划算法

摘要：本文通过研究动态规划原理，提出了根据该原理解决０／１背包问题的方法与算法实现，并对算法的正确性作了验证．观察程序运行结果，发现基于动态规划的算法能够得到正确的决策方案且比穷举法有效．

关键字：动态规划；０／１背包；约束条件；序偶；决策序列；支配规则

1、引 言

科学研究与工程实践中，常常会遇到许多优化问题，而有这么一类问题，它们的活动过程可以分为若干个阶段，但整个过程受到某一条件的限制。这若干个阶段的不同决策的组合就构成一个完整的决策。0/1背包问题就是一个典型的在资源有限的条件下，追求总的收益最大的资源有效分配的优化问题。

对于0/1背包问题，我们可以这样描述：设有一确定容量为C的包及两个向量C’=（S1，S2，……，Sn）和P=（P1，P2，……，PN），再设X为一整数集合，即X=1，2，3，……，N，X为SI、PI的下标集，T为X的子集，那么问题就是找出满足约束条件∑Si〈=C，使∑PI获得最大的子集T。在实际运用中，S的元素可以是N个经营项目各自所消耗的资源，C可以是所能提供的资源总量，P的元素可是人们从各项项目中得到的利润。

0/1背包问题是工程问题的典型概括，怎么样高效求出最优决策，是人们关心的问题。

2、求解问题的动态规划原理与算法

2．1动态规划原理的描述

求解问题的动态规划有向前处理法向后处理法两种，这里使用向前处理法求解0/1背包问题。对于0/1背包问题，可以通过作出变量X1，X2，……，XN的一个决策序列来得到它的解。而对于变量X的决策就是决定它是取0值还是取1值。假定决策这些X的次序为Xn，XN-1，……，X0。在对X0做出决策之后，问题处于下列两种状态之一：包的剩余容量是M，没任何效益；剩余容量是M-w，效益值增长了P。显然，之后对Xn-1，Xn-2，……，X1的决策相对于决策X所产生的问题状态应该是最优的，否则Xn，……，X1就不可能是最优决策序列。如果设Fj（X）是KNAP（1，j，X）最优解的值，那么Fn（M）就可表示为

要求：编写程序，用动态规划法求解0—1背包问题。

一、 实验目的与要求

1、明确0-1背包问题的概念

2、利用动态规划解决0-1背包问题问题

二、实验题：

0-1背包问题(knapsack problem)， 某商店有n个物品，第i个物品价值为vi，重量(或称权值)为wi，其中vi和wi为非负数, 背包的容量为W，W为一非负数。目标是如何选择装入背包的物品， 使装入背包的物品总价值最大，所选商品的一个可行解即所选商品的序列如何？背包问题与0-1背包问题的不同点在于，在选择物品装入背包时，可以只选择物品的一部分， 而不一定要选择物品的全部。可将这个问题形式描述如下：

约束条件为：

举例:

若商店一共有5类商品，重量分别为：3，4，7，8，9

价值分别为：4，5，10，11，13

则：所选商品的最大价值为24

所选商品的一个序列为：0 0 0 1 1

三、实验代码

#include

#include

#include

int min(int w,int c)

{int temp;

if (w

else

temp=c;

return temp;

}

int max(int w,int c)

{

int temp;

if (w>c) temp=w; niiixv1max}1,0{,1iniiixWxwelse

temp=c;

return temp;

}

void knapsack(int v[],int w[],int c,int n,int**m) //求最优值

{

int jmax=min(w[n]-1,c);

for(int j=0;j<=jmax;j++)

m[n][j]=0;

for(int jj=w[n];jj<=c;jj++)

m[n][jj]=v[n];

for(int i=n-1;i>1;i--){ //递归部分

（３）确定哪些物品被装入背包　为了确定具体那件物品被装入背包，需要从Ｖ（４，　１０）＝１１向前推。根据公式５，如果Ｖ（ｎ，Ｃ）＞ｖ（ｎ一１，　Ｃ），则表明第ｎ个物品被装入背包。　ａ）Ｖ（４，１０）＞Ｖ（３，１０），说明第４件物品被装入　背包，即ｘ４＝１，ｊ＝１０．５＝５。　ｂ）Ｖ（３，５）＝Ｖ（２，５），说明第３件物品没有被装　入背包，即ｘ　ｆ＿Ｏ，ｊ不变还是５。　ｃ）Ｖ（２，５）＝Ｖ（１，５），说明第２件物品没有被装　入背包，即ｘ２＝０，ｉ不变还是５。　ｄ）Ｖ（１，５）＞Ｖ（０，５），说明第１件物品被装入背　包，即ｘｌ＝１，ｊ＝５—３＝２。　由以上分析可知，装入背包的物品为ｘ＝｛１，０，０，　１｝。即第１、４件物品被装入背包。　．　互联网　：　＿本期　２．５　０．１背包问题的应用　０．１背包问题可以被应用到许多领域，在日常生活中也经　常遇到类似的问题。比如每逢节假日各大商场都会推出各种　促销活动，如购物满５００元赠２００元现金券，并且现金券只能　购物不找余额。这个购物问题就可以通过０—１背包问题解决，　假定要购买１Ｏ件商品，每件商品有两项指标：一个是重要度，　分为４等，用１～４表示，数值越大表示该商品越重要；另一个　是商品的价格。因此该购物问题就可以转换为如何选择这些　商品使重要度　价格的和最大，且不超过７００元的限制条件。　３结束语　求解０．１背包问题的算法可分为两大类：近似算法和精　确算法，每种算法的时间复杂度和收敛速度各不相同。动态　规划法属于精确算法，适用于规模较小的背包问题。本文归　纳了利用动态归纳法求￣￣ｏ－１背包问题的过程，并举例说明。　参考文献：　［１】王晓东．计算机算法设计与分析［Ｍ】．北京：电子工业出版社，２０１２．　［２］刘继，夏定纯．用动态规划法与回溯法实现０—１背包问题的比较［Ｊ】．科技信息，２　０１０（１　９）：４５８．　作者简介：于洋（１９７６．０１＇－），女，山东章丘人，教师，讲师，硕士研究生，研究方向：Ｗｅｂ应用开发、网站制作。　作者单位：辽宁省交通高等专科学校，沈阳　１１０１２２　《《《《《《上接第１０２页　景执行的部分有两个，第一就是自动化快照，系统将会自　动的对指定的虚拟机进行快照，然而快照建立完成后会备　份一份到外部的ＮＡＳ空间，然而为了要提升备份的可靠　度，可以使用丛集系统当作备储存系统，相对可以提高传　输效率又可以提升备份的可靠度，但由于本研究的环境限　制，目前使用一台主机当作ＮＡＳ。然而第二项就是自动化　还原，系统将会定期侦测虚拟机的状态以及发送封包，当　系统发生错误时，自动化还原机制将会自动使用最新的快　照进行还原的动作，以确保使用者的损失降到最低。　３云计算技术在信息资源共享优化中需要重视的问题　将需要使用完整型的快照去进行还原，透过本研究　的测试，为了让使用者使用起来不但有最高等级的容错机　制，亦不会影响使用者的使用，为此我们选择了每三个小　时执行一次完整型快照搭配每一个小时执行一次快速型快　照，而在中级型，使用者主要保护的是虚拟机中的档案系　统，因此将拉长两个完整型快照的间隔，相对减少了中断　服务的时间，但当发生错误要进行还原时，如果需要包含　程式执行的状态，与高级的相比，将会损失较多的资料。　在建立快照后，本系统将会把快照储存在两个地方（本机　端、外部储存空间），除了本身产生快照的位置之外，为　了防止实体机器发生错误时，连同虚拟机以及快照档案一　同消失不见，因此在建立快照完成后，本机制将会备份一　份到外部的储存空间中，当使用者在建立完成虚拟机时，　本机制也会备份一份虚拟机的档案（ｑｃｏｗ２）到外部储存　空间中，为此使用者将会又多了一道保护的措施，将系统　发生错误的损失降到最低。提升了云端平台的服务品质，　主要保护的对象为虚拟机，我们无法预知实体机器何时会　出现异常，当实体机器发生问题时，在上头运行的虚拟机　也连带会受到影响，可能最严重的情况为实体机无法运　作，这时候就算有快照，也无法把虚拟机恢复成原来的状　态，毕竟快照是存在该台实体机中，为了预防发生这种状　况，我们将快照备份到外部的储存空间中，当遇到这种情　况时，才有快照可以将虚拟机恢复成原来运行的状态，将　损失降到最低。　４结束语　云计算描述了一种可以通过互联网进行访问的可扩展　的应用程序。云计算使用大规模的数据中心以及功能强劲　的服务器来运行网络应用程序与网络服务。任何一个用户　通过合适的互联网接入设备以及一个标准的浏览器都能够　访问一个云计算应用程序。　参考文献：　［１】何超，张玉峰．基于ｗｅｂ链接挖掘的馆藏资源语义聚合与可视化展示研究［Ｊ］．情报科学，２０１　５（０２）：１１５—１２０．　［２］刘道新，胡航海，张健．大数据全生命周期中关键问题研究及应用…．中国电机工程学报，２０１　５（０１）：２　３－２８．　［３】秦利，王晓云，赵晋巍．科技信息资源开发利用现状与对策研究［Ｊ】．情报理论与实践，２０１５（０１）：１　８－２２．　【４］李华，陈立云，左军．浅析数据挖掘技术在高等院校信息资源建设中发挥的作用［Ｊ］．电子技术与软件工程，２０１４（０１）：２１９．　作者简介：冯宇（１９７４．１２－），男，辽宁辽阳人，教师，讲师，工程硕士，本科，研究方向：计算机网络技术、计算机　应用技术。　作者单位：渤海船舶职业学院信息工程系，辽宁兴城１　２５１０５　磨　ＣＤ　Ｓｏｆｔｗａｒｅ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ／１　

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

⼀、动态规划

状态转移⽅程：

1 从前往后：

2 if(j>=w[i])

3 m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);

4 else

5 m[i][j]=m[i-1][j];

6

7 从后往前：

8 if(j>=w[i])

9 m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);

10 else

11 m[i][j]=m[i+1][j];

算法：

1 从前往后：

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

3 for(int j=1;j<=c;j++)

4 {

5 if(j>=w[i])

6 {

7 m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);

8 }

9 else//这⾥没有考虑j<0的情况，因为算法中j取不到

10 {

11 m[i][j]=m[i-1][j];

12 }

13 }

14

15 从后往前：

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

17 for(int j=1;j<=c;j++)

18 {

19 if(j>=w[i])

20 {

21 m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);

22 }

23 else

24 {

25 m[i][j]=m[i+1][j];

26 }

27 }

例⼦：

例：0-1背包问题。在使⽤动态规划算法求解0-1背包问题时，使⽤⼆维数组m[i][j]存储背包剩余容量为j，可选物品为i、i+1、……、n时0-1背包问题的最

优值。绘制

重量数组w = {4, 6, 2, 2, 5, 1}，

价值数组v = {8, 10, 6, 3, 7, 2}，

背包容量C = 12时对应的m[i][j]数组。（从前往后）

例题代码 :

1 #include

2 #include

3 #include

4 #define N 20