论文部分内容阅读
摘 要： 0/1背包问题是实际当中经常遇到的一类经典NP难组合优化问题之一.本文分别对贪心法、动态规划、回溯法这三种设计方法进行求解和算法分析，并通过公共测试数据集对各种算法的效果进行了对比，得出了0/1背包问题不同算法的适用范围，为该技术的推广应用奠定了基础。
关键词： 0/1背包问题；贪心法；动态规划；回溯法
【中图分类号】 TP301 【文献标识码】 A【文章编号】 2236-1879（2018）09-0200-02
0 引言
0/1背包问题[1]（knapsack problem）是计算机学科中的一个经典的NP难组合优化问题之一.问题可以描述为：假设给定1个背包，背包内可以容纳n种物品（单个物品的重量是，价值为，），背包的总容量为.0/1背包问题就是求从这 n 件物品中选择部分物品且对物品不能重复选择，满足所选择物品的总重量不超过且总价值最大.如果xi表示物品被选择的情况，.当时，表示物品不被选择；当时，表示物品被选择，物品只能被选择一次或者不选.根据问题描述，可以将该问题转化为如下的约束条件（1）（2）和目标函数（3）：
由式（1-3）可知，0/1背包问题可以转化为寻找在满足约束条件（1）（2）条件下，同时使得目标函数式（3）达到最大的解向量
1.贪心法求解0/1背包问题
0/1背包问题的三种贪心策略，每种策略都需要经过多个步骤来完成，每一步都要用贪心策略选择一个物品放入背包中.第一种是重量贪心策略，即从剩下的物品中选择重量最轻的装入背包中，一直下去，直到不满足约束条件；第二种是价值贪心策略；第三种是价值重量比vi/wi贪心策略本文对这三种贪心策略进行了测试，并比较了三种策略的优劣.算法步骤如下：
（1）所有物品按重量从小到大排序（或按价值从大到小排序或计算每种物品的价值重量比vi/wi，然后按价值重量比从大到小排序）；
（2）若将某物品装入背包后，物品总重量不超过W，则选择重量次小的（或价值次高的或价值重量比次高的）物品装入背包.
（3）以此策略一直进行下去，直到物品总重量超过W，最后一件物品不选择为止.
（4）计算放入背包中的所有物品的总价值.
2 动态规划求解0/1背包问题
（4）根据计算最优值时得到的信息，构造一个最优解.
3 回溯法求解0/1背包问题
使用回溯法求解0/1背包问题的算法步骤为：
（1）排序：将背包内物品按照价值重量比（vi/wi）的非增顺序进行排列.
（2）初始化：将当前背包重量w的值设置为0，当前物品的总价值v设置为0，当前搜索深度i为0，当前解向量为x[i]=0，当前最优值v为0.
（3）调用函数：调用限界函数.
（4）如果返回的物品价值大于当前最优值v，则把物品i装入背包中，直至没有物品可装或装不下物品k为止，并生成部分解.转步骤（5）；否则，转步骤（6）.
（5）如果选择的物品数量k大于或等于物品总数量n，则得到一个可行解，并把该可行解的值作为当前最优值，令i=n，转步骤（3），以便回溯搜索其他可行解；否则，令i=k+1，拒绝物品k，从物品k+1继续装入，转步骤（3）.
（6）当k>=0且x[k]=0时，令k=k-1，直至条件不成立.
（7）如果k<0，算法结束；否则，转步骤8.
（8）令x[k]=0，W=W-w[k]，v=v-v[k]，i=k+1，转步骤（3）.
4 实验结果及分析
4.1实验结果。
实验选取背包测试数据中的3个背包数据，背包01为n=8，W=200（n为物品数量，W为物品总重量），背包04为n=30， W=300，背包05为n=100，W=1000.对这3个背包中的测试数据采用以上三种算法进行求解，结果如表1-表5所示.
4.2实验结果分析。
对于每个背包而言，贪心法基本上都无法得到最优解；对于背包内物品数量和重量相对较小时，动态规划方法和回溯法都得到了最优解，回溯法用时较长，但对于物品数量和重量比较大时回溯法将会耗时数天，算法失效，动态规划方法仍然可以得到最优解；因此，动态规划方法无论在物品数量和背包重量多大的情況下均能表现出优良的性能.
5 结语
以上是对贪心方法，动态规划，回溯法这三种常用算法设计方法原理的概要介绍，并分别应用这三种算法求解公共背包测试数据集中的0/1背包问题，根据求解结果对各种设计方法的算法进行了分析.
参考文献
[1] 教材编写组.运筹学[M].北京：清华大学出版社，2005.06
[2] 于秀霞. 求解背包问题的新型算法[J].长春大学学报.2002，4.
关键词： 0/1背包问题；贪心法；动态规划；回溯法
【中图分类号】 TP301 【文献标识码】 A【文章编号】 2236-1879（2018）09-0200-02
0 引言
0/1背包问题[1]（knapsack problem）是计算机学科中的一个经典的NP难组合优化问题之一.问题可以描述为：假设给定1个背包，背包内可以容纳n种物品（单个物品的重量是，价值为，），背包的总容量为.0/1背包问题就是求从这 n 件物品中选择部分物品且对物品不能重复选择，满足所选择物品的总重量不超过且总价值最大.如果xi表示物品被选择的情况，.当时，表示物品不被选择；当时，表示物品被选择，物品只能被选择一次或者不选.根据问题描述，可以将该问题转化为如下的约束条件（1）（2）和目标函数（3）：
由式（1-3）可知，0/1背包问题可以转化为寻找在满足约束条件（1）（2）条件下，同时使得目标函数式（3）达到最大的解向量
1.贪心法求解0/1背包问题
0/1背包问题的三种贪心策略，每种策略都需要经过多个步骤来完成，每一步都要用贪心策略选择一个物品放入背包中.第一种是重量贪心策略，即从剩下的物品中选择重量最轻的装入背包中，一直下去，直到不满足约束条件；第二种是价值贪心策略；第三种是价值重量比vi/wi贪心策略本文对这三种贪心策略进行了测试，并比较了三种策略的优劣.算法步骤如下：
（1）所有物品按重量从小到大排序（或按价值从大到小排序或计算每种物品的价值重量比vi/wi，然后按价值重量比从大到小排序）；
（2）若将某物品装入背包后，物品总重量不超过W，则选择重量次小的（或价值次高的或价值重量比次高的）物品装入背包.
（3）以此策略一直进行下去，直到物品总重量超过W，最后一件物品不选择为止.
（4）计算放入背包中的所有物品的总价值.
2 动态规划求解0/1背包问题
（4）根据计算最优值时得到的信息，构造一个最优解.
3 回溯法求解0/1背包问题
使用回溯法求解0/1背包问题的算法步骤为：
（1）排序：将背包内物品按照价值重量比（vi/wi）的非增顺序进行排列.
（2）初始化：将当前背包重量w的值设置为0，当前物品的总价值v设置为0，当前搜索深度i为0，当前解向量为x[i]=0，当前最优值v为0.
（3）调用函数：调用限界函数.
（4）如果返回的物品价值大于当前最优值v，则把物品i装入背包中，直至没有物品可装或装不下物品k为止，并生成部分解.转步骤（5）；否则，转步骤（6）.
（5）如果选择的物品数量k大于或等于物品总数量n，则得到一个可行解，并把该可行解的值作为当前最优值，令i=n，转步骤（3），以便回溯搜索其他可行解；否则，令i=k+1，拒绝物品k，从物品k+1继续装入，转步骤（3）.
（6）当k>=0且x[k]=0时，令k=k-1，直至条件不成立.
（7）如果k<0，算法结束；否则，转步骤8.
（8）令x[k]=0，W=W-w[k]，v=v-v[k]，i=k+1，转步骤（3）.
4 实验结果及分析
4.1实验结果。
实验选取背包测试数据中的3个背包数据，背包01为n=8，W=200（n为物品数量，W为物品总重量），背包04为n=30， W=300，背包05为n=100，W=1000.对这3个背包中的测试数据采用以上三种算法进行求解，结果如表1-表5所示.
4.2实验结果分析。
对于每个背包而言，贪心法基本上都无法得到最优解；对于背包内物品数量和重量相对较小时，动态规划方法和回溯法都得到了最优解，回溯法用时较长，但对于物品数量和重量比较大时回溯法将会耗时数天，算法失效，动态规划方法仍然可以得到最优解；因此，动态规划方法无论在物品数量和背包重量多大的情況下均能表现出优良的性能.
5 结语
以上是对贪心方法，动态规划，回溯法这三种常用算法设计方法原理的概要介绍，并分别应用这三种算法求解公共背包测试数据集中的0/1背包问题，根据求解结果对各种设计方法的算法进行了分析.
参考文献
[1] 教材编写组.运筹学[M].北京：清华大学出版社，2005.06
[2] 于秀霞. 求解背包问题的新型算法[J].长春大学学报.2002，4.