第 4 章 背包问题 如果给你一个背包，要你从许多东西里选择一些装进来，只要这个包装得下，你就可以将包里的东西全部拿走了，那么你会如何选择物品呢？这里你需要考虑的是背包的体积和承重限制，当然最重要的是你拿走的东西的总价值最大。这样的问题就是背包问题，许多问题都可以转化为背包问题来考虑。背包问题是一个在运筹学领域里常见的典型 NP-C难题，对该问题的求解方法的研究无论是在理论上，还是在实践中都具有一定的意义。 对于背包问题，已有的求解方法可分为 （ 1）精确算法：动态规划法，回溯法，分支定界法； （ 2）近 似算法：贪婪法，拉格郎日法，蚂蚁算法，遗传算法。 4.1 用贪心法解决背包问题 4.1.1案例 1 最佳装载 需对容量为 c 的背包进行装载。从 n 个物品中选取装入背包的物品，每件物品 i 的重量为 wi，价值为 pi。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高 。 第一行和第二行为物品的总数量和背包的容量，第三行和第四行为第一个物品的重量和价值，第五行和第六行为第二个物品的重量和价值 价值最高的解决方案：每种物品要装载的数量 5 20 77 第 4 章 背包问题 6 3 2 5 3 8 10 6 7 4 0 1 1 1 0.714286 贪心方法：总是对当前的问题作最好的选择，也就是局部寻优。最后得到整体最优。这个题目可以用贪婪法解决，先按物品效益、重量比值升序排序。然后每次选比值大的物品进行装载，直到装满背包为止。 数据结构与算法： 不需要特殊的数据结构 算法采用贪婪法 首先输入物品信息和背包容量 ,然后每次选比重最大的装载。 struct goodinfo float p; /物品效益 float w; /物品重量 float X; /物品该放的数量 int flag; /物品编号 ; /物品信息结构体 void Insertionsort(goodinfo goods,int n) int j,i; for(j=2;jgoodsi.p) goodsi+1=goodsi; i-; goodsi+1=goods0; /按物品效益，重量比值做升序排列 void bag(goodinfo goods,float M,int n) float cu; int i,j; for(i=1;icu) /当该物品重量大与剩余容量跳出 break; goodsi.X=1; cu=cu-goodsi.w; /确定背包新的剩余容量 if(in; goods=new struct goodinfo n+1;/ coutM; coutgoodsi.w; coutgoodsi.p; goodsi.p=goodsi.p/goodsi.w; /得出物品的效益，重量比 cout to run agian to exitj; 80 ACM 程序设计培训教程 4.2 回溯法解决背包问题 (0-1) 4.2.1 案例 2 0/1 背包 需对容量为 c 的背包 进行装载。从 n 个物品中选取装入背包的物品，每件物品 i 的重量为wi，价值为 pi。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高 。限制：每个物品不能被分割，要不被装载，要不不被装载。 第一行物品个数，接下来分别为物品价值，再接下来分别为物品的重量。最后为背包的容量。 第一行为最佳装载的信息（ 1 代表该物品被装载， 0 代表该物品没有被装载），第二行为最佳装载的总价值。 5 9 20 1 6 7 6 1 8 9 2 20 1 1 0 1 1 42 0 1 背 包问题是一个子集选取问题，适合于用子集树表示 0 1 背包问题的解空间。在搜索解空间树是，只要其左儿子节点是一个可行结点，搜索就进入左子树，在右子树中 81 第 4 章 背包问题 有可能包含最优解是才进入右子树搜索。否则将右子树剪去。 数据结构与算法： 不需要特殊的数据结构 采用回溯法解决 #include using namespace std; class Knap friend int Knapsack(int p,int w,int c,int n ); public: void print() for(int m=1;mn) if(bestpbestp) /搜索右子树 xi=0; Backtrack(i+1); class Object 83 第 4 章 背包问题 friend int Knapsack(int p,int w,int c,int n); public: int operator=a.d); private: int ID; float d; ; int Knapsack(int p,int w,int c,int n) /为 Knap:Backtrack初始化 int W=0; int P=0; int i=1; Object *Q=new Objectn; for(i=1;in; p=new intn+1; w=new intn+1; p0=0; w0=0; coutpi; coutwi; 85 第 4 章 背包问题 coutc; cout #include #include #include #include using namespace std; /定义问题的最大规模 #define max 100 /问题规模，即共有多少个包 int packageNum; /每个包的重量 int packageWeightmax; /每个包的价值 int packageValuemax; /约束，背包的最大容量 int limitWeight; /群体的规模 int colonySize; /colonyStateik 表示一个染色体 /colonyState1.colonySize 0|1 表示一代群体 int colonyStatemax2max; / currAge 表示当前代的编号 / (currAge+1)%2 表示下一代的编号 int currAge = 0; /个体评价信息表 typedef struct tagIndividualMsg int index; int value; IndividualMsg; IndividualMsg individualMsgmax; / 87 第 4 章 背包问题 / 函数声明 void printColonyState( int nextAge ); / /初始化群体 void colonyInit() int i , j; int w; for( i = 0 ; i limitWeight ) w = 0; for( j = 0 ; j value - x-value; void individualEstimate() int i , j; for( i = 0 ; i = 0 ; i- ) wheeli=(individualMsgi.value+wheeli+1)+colonySize*(colonySize-i); int seed = abs( wheel0 - ( rand() % ( 2 * wheel0 ) + 1 ) ); choose = colonySize - 1; while( seed wheelchoose ) choose-; return choose; /交叉 void across( int male , int female , int index ) int nextAge = (currAge+1)%2; int i , j , t; int acrossBit = rand() % (packageNum-1) + 1; for( j = 0 ; j limitWeight ) /随机生成新的个体 w = limitWeight + 1; while( w limitWeight ) w = 0; for( j = 0 ; j = 0 ) for( j = 0 ; j packageNum; w=new intpackageNum; v=new intpackageNum; coutvi; coutwi; for( i = 0 ; i limitWeight; colonySize = 5; delete w; delete v; void printProblem() int i; cout; if( k = currAge ) cout /*/*N 定义为 7，即有 7 件物品； S 定义为 15，即背包能放的重量为15，比如 15公斤 */ #define N 7 #define S 15 int wN+1 = 0,1,4,3,4,5,2,7;/*/*给定各物品的重量值，放入数组 wN+1中 */ int knap(int s,int n) /*/*knap函数递归计算出符合选择要求的物品，并显示其 重量。形参 s 实际是放入物品 i后，背包还能装 载的重量， n为考查物品 i后下一个待考查的物品。 */ if(s = 0) return 1; /*/*如果 s等于 0时返回 0并退出 knap函数 */ if ( s0 & n0同时 n1则返回 0*/ if (knap(s-wn,n-1) /*/*考查物品 n被选择的情况 */ printf(%d ,wn); /*/*在屏幕上打印被选择的物品的重量 */ return 1; /*/*返回 1*/ return knap(s,n-1); /*/*考查不选择物品 n的情况 */ 95 第 4 章 背包问题 main() if (knap(S,N) printf( OK! );/*/*如果 knap最终返回 1，打印 OK! 则表示成功选出一组物品 */ else printf( N0! ); /*/*否则打印 NO！表示没有选出合适的一组 !*/