论文部分内容阅读
【摘 要】背包问题是算法设计中的经典问题。本文对不同的背包问题、解决背包问题的几种常用算法设计技术及几种不同贪心准则进行了介绍。并通过对不同贪心准则的讨论，给出了一个解决连续背包问题最优解的贪心准则并用C语言程序得以实现。
【关键词】连续背包问题；贪心算法；最优解
背包问题是在1978年由Merkel和Hellman提出的。背包问题有很大的理论与应用价值，在金融领域的投资决策、预算决策、项目选择、资源分配和货物装载等方面均有重要的应用。背包问题的实质就是优化的问题，即如何在有效的空间内装载更多的物品，实现背包价值的最大化。因此背包问题的最优解问题已经成为当前研究的一大热点和重点，它有助于提升应用的水平，加快效率社会的建设步伐。本文主要通过对不同的背包、解决背包问题的几种常用算法设计技术及几种不同贪心准则的讨论，给出了一个解决连续背包问题最优解的贪心准则并用C语言程序得以实现。
1.背包问题的分类
现在我们讨论的是用一维状态实现背包问题，它可以分为以下几类：
连续背包问题：有n件物品和一个载荷能力为m的背包。第i件物品的重量是，价值是。求解将哪些物品的部分装入背包可使这些物品的总重量不超过背包容量，且价值总和最大。
0/1背包问题：有n件物品和一个载荷能力为m的背包。第i件物品的重量是，价值是。求解将哪些物品装入背包可使这些物品的总重量不超过背包容量，且价值总和最大。它是最基础的背包问题，包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成0/1背包问题求解。其特点是：每种物品仅有一件，可以选择放或不放。
多重背包问题：有n种物品和一个载荷能力为m的背包。第i种物品最多有q件可用，每件重量是，价值是。求解将哪些物品装入背包可使这些物品的总重量不超过背包容量，且价值总和最大。将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别1，2，4，...，2^（k-1），q-2^k+1，且k是满足n-2^k+1>0的最大整数。例如，如果q为13，就将这种物品分成系数分别为1，2，4，6的四件物品。分成的这几件物品的系数和为q，表明不可能取多于q件的第i种物品。另外这种方法也能保证对于0..q间的每一个整数，均可以用若干个系数的和表示，这个证明可以分0..2^k-1和2^k..q两段来分别讨论得出。
完全背包问题：有n种物品和一个载荷能力为m的背包，每种物品都有无限件可用。第i种物品的的重量是，价值是。求解将哪些物品装入背包可使这些物品的总重量不超过背包容量，且价值总和最大。
2.解决背包问题的常用算法设计技术
贪心算法是一种在每一步选择中都采取在当前状态下最优的选择，从而希望导致结果是最优的算法。它是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪心算法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的。
贪心法有一个共同的点就是在最优求解的过程中都采用一种局部最优策略，把问题范围和规模缩小，最后把每一步的结果合并起来得到一个全局最优解。
下面介绍常用的三种贪心准则：
价值贪心准则：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一個价值最大的物品。如此继续下去，这种策略不能保证得到最优解。
重量贪心准则：从剩下的物品中选择可装入背包的重量最小的物品。在一般情况下也不一定能得到最优解。
价值密度/贪心准则：从剩余物品中选择可装入包的/值最大的物品，即按/递减的次序装入物品，这种策略对于连续背包问题可保证得到最优解。
3.用C语言实现贪心算法求解连续背包问题最优解
连续背包问题的最优贪心准则是价值密度贪心准则，其证明的基本思路是：把通过价值密度贪心准则获得的贪心解与任一可行解比较，若这两个解不同，就开始寻找第一个不同的，然后设法用贪心解的去替换可行解的对应分量，并证明可行解在分量替换后的总价值总是大于等于未替换前的值。反复进行这种替换，直到新产生的可行解等于贪心解，即最优解。若令x=[，……，]为用价值密度贪心准则获得的解，y=[，……，]为任意一个可行解，只需证明不失一般性，可以假设物品都按价值密度=/递减排好了序，即（1in），然后分几步用贪心解的去替换可行解的对应分量，将转化为，转换过程中每一步都产生一个可行的新，且大于等于未转化前的值，最后便可证明。以下图1是利用C语言实现贪心算法求解连续背包问题最优解的程序流程图，图2是其中的Pi/wi降序排列子程序流程图。
下面考虑该领域常用的一个例子： n=7，m=15，p=[10，5，15，7，6，18，3]，w=[2，3，5，7，1，4，1]，程序分别对pi/wi价值密度、价值进行降序排列，重量进行升序排列，再应用三种贪心算法进行顺序装入，直到背包被装满。得到三种准则的解并进行比较得到最优解。所得结果显然可知价值密度贪心准则为连续背包问题最优解的贪心准则。
参考文献：
[1]M.H.Alsuwaiyel.算法设计技巧与分析[M].北京：电子工业出版社，2004.
[2]任瑞证，严蔚敏.整数背包问题的应用及其算法研究[J].型微型计算机系统，2001，22（2）：204—206.
[3]游维.基于贪婪策略的0/1背包问题算法研究[J].计算机与现代化，2007，4：10-12，16.
作者简介：
林宏（1976-），女，硕士，闽江学院物理学与电子信息工程系讲师，研究方向：计算机软件及算法。
【关键词】连续背包问题；贪心算法；最优解
背包问题是在1978年由Merkel和Hellman提出的。背包问题有很大的理论与应用价值，在金融领域的投资决策、预算决策、项目选择、资源分配和货物装载等方面均有重要的应用。背包问题的实质就是优化的问题，即如何在有效的空间内装载更多的物品，实现背包价值的最大化。因此背包问题的最优解问题已经成为当前研究的一大热点和重点，它有助于提升应用的水平，加快效率社会的建设步伐。本文主要通过对不同的背包、解决背包问题的几种常用算法设计技术及几种不同贪心准则的讨论，给出了一个解决连续背包问题最优解的贪心准则并用C语言程序得以实现。
1.背包问题的分类
现在我们讨论的是用一维状态实现背包问题，它可以分为以下几类：
连续背包问题：有n件物品和一个载荷能力为m的背包。第i件物品的重量是，价值是。求解将哪些物品的部分装入背包可使这些物品的总重量不超过背包容量，且价值总和最大。
0/1背包问题：有n件物品和一个载荷能力为m的背包。第i件物品的重量是，价值是。求解将哪些物品装入背包可使这些物品的总重量不超过背包容量，且价值总和最大。它是最基础的背包问题，包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成0/1背包问题求解。其特点是：每种物品仅有一件，可以选择放或不放。
多重背包问题：有n种物品和一个载荷能力为m的背包。第i种物品最多有q件可用，每件重量是，价值是。求解将哪些物品装入背包可使这些物品的总重量不超过背包容量，且价值总和最大。将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别1，2，4，...，2^（k-1），q-2^k+1，且k是满足n-2^k+1>0的最大整数。例如，如果q为13，就将这种物品分成系数分别为1，2，4，6的四件物品。分成的这几件物品的系数和为q，表明不可能取多于q件的第i种物品。另外这种方法也能保证对于0..q间的每一个整数，均可以用若干个系数的和表示，这个证明可以分0..2^k-1和2^k..q两段来分别讨论得出。
完全背包问题：有n种物品和一个载荷能力为m的背包，每种物品都有无限件可用。第i种物品的的重量是，价值是。求解将哪些物品装入背包可使这些物品的总重量不超过背包容量，且价值总和最大。
2.解决背包问题的常用算法设计技术
贪心算法是一种在每一步选择中都采取在当前状态下最优的选择，从而希望导致结果是最优的算法。它是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪心算法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的。
贪心法有一个共同的点就是在最优求解的过程中都采用一种局部最优策略，把问题范围和规模缩小，最后把每一步的结果合并起来得到一个全局最优解。
下面介绍常用的三种贪心准则：
价值贪心准则：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一個价值最大的物品。如此继续下去，这种策略不能保证得到最优解。
重量贪心准则：从剩下的物品中选择可装入背包的重量最小的物品。在一般情况下也不一定能得到最优解。
价值密度/贪心准则：从剩余物品中选择可装入包的/值最大的物品，即按/递减的次序装入物品，这种策略对于连续背包问题可保证得到最优解。
3.用C语言实现贪心算法求解连续背包问题最优解
连续背包问题的最优贪心准则是价值密度贪心准则，其证明的基本思路是：把通过价值密度贪心准则获得的贪心解与任一可行解比较，若这两个解不同，就开始寻找第一个不同的，然后设法用贪心解的去替换可行解的对应分量，并证明可行解在分量替换后的总价值总是大于等于未替换前的值。反复进行这种替换，直到新产生的可行解等于贪心解，即最优解。若令x=[，……，]为用价值密度贪心准则获得的解，y=[，……，]为任意一个可行解，只需证明不失一般性，可以假设物品都按价值密度=/递减排好了序，即（1in），然后分几步用贪心解的去替换可行解的对应分量，将转化为，转换过程中每一步都产生一个可行的新，且大于等于未转化前的值，最后便可证明。以下图1是利用C语言实现贪心算法求解连续背包问题最优解的程序流程图，图2是其中的Pi/wi降序排列子程序流程图。
下面考虑该领域常用的一个例子： n=7，m=15，p=[10，5，15，7，6，18，3]，w=[2，3，5，7，1，4，1]，程序分别对pi/wi价值密度、价值进行降序排列，重量进行升序排列，再应用三种贪心算法进行顺序装入，直到背包被装满。得到三种准则的解并进行比较得到最优解。所得结果显然可知价值密度贪心准则为连续背包问题最优解的贪心准则。
参考文献：
[1]M.H.Alsuwaiyel.算法设计技巧与分析[M].北京：电子工业出版社，2004.
[2]任瑞证，严蔚敏.整数背包问题的应用及其算法研究[J].型微型计算机系统，2001，22（2）：204—206.
[3]游维.基于贪婪策略的0/1背包问题算法研究[J].计算机与现代化，2007，4：10-12，16.
作者简介：
林宏（1976-），女，硕士，闽江学院物理学与电子信息工程系讲师，研究方向：计算机软件及算法。