-背包问题求解方法综述.doc

精选文档，供参考！
页脚下载后可删除，如有侵权请告知删除！
精选文档，供参考！
算法分析与设计大作业
实验题目：0-1背包问题求解方法综述
组 员：
班　　级：
指导教师：
精选文档，供参考！
页脚下载后可删除，如有侵权请告知删除！
精选文档，供参考！
0-1背包问题求解方法综述
【摘要】：0-1背包问题是一个经典的NP-hard组合优化问题，现实生活中的很多问题都可以以它为模型。本文首先对背包问题做了阐述，然后用蛮力解法、动态规划算法、贪心算法和回溯解法对背包问题进展求解，分析了0-1背包问题的数学模型,刻划了最优解的构造特征,建立了求最优值的递归关系式。最后对四种算法从不同角度进展了比照和总结。
【关键词】：0-1背包问题；蛮力解法；动态规划算法；贪心算法；回溯解法。

0-1背包问题是指给定n个物品,每个物品均有自己的价值vi和重量wi(i=1,2,…,n),再给定一个背包,其容量为W。要求从n个物品中选出一局部物品装入背包,这局部物品的重量之和不超过背包的容量,且价值之和最大。单个物品要么装入,要么不装入。很多问题都可以抽象成该问题模型,如配载问题、物资调运[1]问题等,因此研究该问题具有较高的实际应用价值。目前,解决0-1背包问题的方法有很多,主要有动态规划法、回溯法、分支限界法、遗传算法、粒子群算法、人工鱼群算法、蚁群算法、模拟退火算法、蜂群算法、禁忌搜索算法等。其中动态规划、回溯法、分支限界法时间复杂性比拟高,计算智能算法可能出现局部收敛,不一定能找出问题的最优解。文中在动态规划法的根底上进展了改良,提出一种求解0-1背包问题的算法,该算法每一次执行总能得到问题的最优解,是确定性算法,算法的时间复杂性最坏可能为O(2n)。
-1背包问题描述
0-1背包问题(KP01)是一个著名的组合优化问题。它应用在许多实际领域,如工程选择、资源分布、投资决策等。背包问题得名于如何选择最适宜的物品放置于给定背包中。本文主要研究背包问题中最根底的0/1背包问题的一些解决方法。
为解决背包问题，大量学者在过去的几十年中提出了很多解决方法。解决背包问题的算法有最优算法和启发式算法[2]，最优算法包括穷举法、动态规划法、分支定界法、图论法等，启发式算法包括贪心算法、遗传算法、蚁群算法、粒子算法等一些智能算法。
精选文档，供参考！
页脚下载后可删除，如有侵权请告知删除！
精选文档，供参考！
0-1背包问题一般描述为：给定n种物品和一个背包。物品i的重量是w(i)，其价值为v(i)，背包的容量为c。问应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？
在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包屡次，也不能只装入局部的物品i。因此，该问题称为0-1背包问题。
此问题的形式化描述是，给定，要求找出一个n元0-1向量，使得，而且到达最大。
数学模型：
约束条件： ，
-1背包问题的求解算法
〔brute force method〕
：
对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍历过的最大价值。
:
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100 //最多可能物体数
struct goods //物品构造体
{
int sign; //物品序号
int w; //物品重量
int p; //物品价值
}a[N];
bool m(goods a,goods b)
精选文档，供参考！
页脚下载后可删除，如有侵权请告知删除！
精选文档，供参考！
{
return ()>();
}
int max(int a,int b)
{
return a<b?b:a;
}
int n,C,bestP=0,cp=0,cw=0;
int X[N],cx[N];
/*蛮力法求解0/1背包问题*/
int Force(int i)
{
if(i>n-1){
if(bestP<cp&&cw+a[i].w<=C){
fo