动态规划求解0-1背包问题(共8页)

1、精选优质文档-倾情为你奉上数学实验论文动态规划算法求解0-1背包问题郭伦()指导教师名：郭德龙职 称：副教授单 位：数学与统计学院专 业 名 称：B15信息与计算科学动态规划算法求解0-1背包问题摘 要本文主要阐述了基于MATLAB的0-1背包问题动态规划的求解。0-1背包问题（Knapsack Problem，简称KP问题）是一个经典的组合优化问题，具有广泛的实际应用背景，以及在理论研究领域也有其相当的代表性。KP问题的求解，在生活中多有应用，如货源分配、轮船装载、项目选择等等都有它的身影。并且它还常常作为其他相对复杂的组合问题的一个特殊解，但当问题规模过大时，如果想要得到最优解是极其困难的

2、，因此对大规模的0-1背包问题的研究无论是在理论研究领域还是实际应用背景都有其重要的意义。动态规划算法是五种常用的算法之一，通常用于求解具有某种最优性质的问题。其基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，

3、只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。由于我们可以用一个表来记录所有已解子问题的答案，需要用到的时候直接调用，所以动态规划法又叫“填表法”。关键词：KP问题，0-1背包问题，动态规划，最优解，背包问题，MATLAB，基于MATLAB的0-1背包问题动态规划的求解一问题重述给定一个容量为C的背包和n个物品，其中物品i的体积为vi,价值为wi(i=1,2,3,n),要从这n个物品中挑选出若干件放入背包，每个物品只能挑选一次，使得放入物品的总体积不超过C，而价值达到最大，并找出一种添放物品的方案。二模型假设0-1背包问题

4、的为：设xi为一个二进制量，xi=1表示将物品i放入背包，xi=0表示物品不装入背包，问题的目的在于确定一个二进制的数组（x1,x2,x3xn）使得maxi=1nxiwi即：maxi=1nxiwi xi(0,1) 且 i=1nxiviC三符号说明C:背包的容量V:物品的体积W:物品的价值n:物品的数量f：用于状态交换的矩阵t：用于输入物品是否装入背包，0表示装入，1表示不装入四问题分析对于0-1背包问题，每个物品都只有两种选择，装入或者不装入两种，可以用一个二维数组fij表示物品是否装入背包。我们要做的是找出可以放入背包的物品使得背包内的价值最大，利用递归思想，用子问题定义状态：即fij表示前

5、i件物品恰放入一个容量为j的背包可以获得的最大价值。则其状态转移方程便是：fij=maxfi-1j,fi-1j-vi+wi对于第i个物品，我们可以拿这个物品的体积同背包内剩余的体积相比较，如果背包内剩余的容量大于物品的体积，那么这个物品就可以装入背包，这时我们只要判断装入这个物品后和装入这个物品前的价值哪一个更大，就可以通过这种递归的方式球的背包能装入的最大价值。五模型建立与求解我们知道，动态规划算法又叫填表法，填表的顺序为自底向上，自左向右，于是我们首先确定第n个物品是否可以被装入背包： if v(n)<=j f(n,j)=w(n) ; else f(n,j)=0; 在通过递归公式fi

6、j=maxfi+1j,fi+1j-vi+wi逐个求解出接下来的解，最后将这些局部最优解填入表格中：由表格中的数据我们不难发现能够装入背包的最大价值，那么，接下来我们根据这个表求解出这个最大价值是由哪集中物品装入而得到的：%3、找出装入背包的所有物品 j=c; for i=1:n-1 if f(i,j)=f(i+1,j) t(i)=0; else t(i)=1; j=j-v(i); end end if f(n,j)=0 t(n)=0; else t(n)=1; end t于是我们就可以得到这个最优解的“路径”：六模型的评价与推广不得不说KP问题是一个经典的动态规划模型，它既简单形象容易理解，又

7、在某种程度上揭示动态规划的本质。有多种方法可以处理它，比如分支限界法、回溯法、贪心算法等等都可以对其进行求解，在这里我们仅选择其中的动态规划，以实例的形式对其求解。七参考文献王晓东-算法设计与分析(第三版)-清华大学出版社乐经良、向隆万、李世栋-数学实验-高等教育出版社八附件Matlab文件基于MATLAB的0-1背包问题的动态规划求解源代码：>> c=15; % 定义背包的最大容量 v= 2 3 6 4 7; % 定义各个物品的体积 w= 10 5 8 16 9; % 定义各个物品对应的价值 n =length(v); % n为物品的数量 f=; %定义一个用于状态交换的矩阵 t

8、=; %用于输出物品是否装入背包的状态 %1、判断第一个物品放或不放for j=1:15 if v(n)<=j f(n,j)=w(n) ; else f(n,j)=0; end end %2、判断下一个物品是否装入。引用递归公式fii=maxfi-1j,fi-1j-vi+wi for i=n-1:-1:1 for j=1:15 if j<=v(i) f(i,j)=f(i+1,j); else if f(i+1,j)>f(i+1,j-v(i)+w(i) f(i,j)=f(i+1,j); else f(i,j)=f(i+1,j-v(i)+w(i); end end end end f%3、找出装入背包的所有物品 j=c; for i=1:n-