Liny_@NotePad

沉迷ACG中

限界与剪枝求解0/1背包问题

YOYO posted @ 2009年6月07日 18:20 in 【算法】与【数据结构】 with tags 分支限界 01背包 , 3326 阅读

一、 算法思想描述

首先对物体按照价值重量比进行排序。
再从第一个物体开始，对每个物体分两种状态求解：放入与不放入。
在每次求解时都计算该状态可能达到的最优价值，并放入大顶堆中。
当两种状态都求解完后从堆中取出堆顶元素，从该元素所代表的状态中继续进行分支计算。直到深度达到n，问题得到解。

二、 完整的程序以及说明

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4.  
  5. //      最多可能物体数
  6. #define N 10
  7.  
  8. //      物体结构体
  9. typedef struct {
  10.         float w;        //      重量
  11.         float p;        //      价值
  12.         float v;        //      价值重量比
  13.         int num;        //      编号
  14. } OBJECT;
  15.  
  16. //      状态结构体
  17. typedef struct {
  18.         bool s1[N];     //   当前放入物体
  19.         int k;    //        搜索深度
  20.         float b;        //      价值上界
  21.         float w;        //      物体重量
  22.         float p;        //      物体价值
  23. } KNAPNODE;
  24.  
  25. //      堆元素结构体
  26. typedef struct {
  27.         KNAPNODE *p;//  结点数据
  28.         float b;        //      所指结点的上界
  29. } HEAP;
  30.  
  31. /*      比较两个物体的价值比 */
  32. bool cmp(OBJECT a, OBJECT b){
  33.         return a.v>b.v;
  34. }
  35.  
  36. /*      交换两个堆元素 */
  37. void swap(HEAP &a, HEAP &b){
  38.         HEAP tmp = a;
  39.         a = b;
  40.         b = tmp;
  41. }
  42.  
  43. /*      堆中元素上移 */
  44. void sift_up(HEAP H[], int i){
  45.         bool done = false;
  46.         if(i!=1){
  47.                 while(!done && i!=1){
  48.                         if(H[i].b>H[i/2].b){
  49.                                 swap(H[i], H[i/2]);
  50.                         }else{
  51.                                 done = true;
  52.                         }
  53.                         i = i/2;
  54.                 }
  55.         }
  56. }
  57.  
  58. /*      堆中元素下移 */
  59. void sift_down(HEAP H[], int n, int i){
  60.         bool done = false;
  61.         if((2*i)<=n){
  62.                 while(!done && ((i = 2*i) <= n)){
  63.                         if(i+1<=n && H[i+1].b > H[i].b){
  64.                                 i++;
  65.                         }
  66.                         if(H[i/2].b<H[i].b){
  67.                                 swap(H[i/2], H[i]);
  68.                         }else{
  69.                                 done = true;
  70.                         }
  71.                 }
  72.         }
  73. }
  74.  
  75. /*      往堆中插入结点 */
  76. void insert(HEAP H[], HEAP x, int &n){
  77.         n++;
  78.         H[n] = x;
  79.         sift_up(H,n);
  80. }
  81.  
  82. /*      删除堆中结点 */
  83. void del(HEAP H[], int &n, int i){
  84.         HEAP x, y;
  85.         x = H[i]; y = H[n];
  86.         n --;
  87.         if(i<=n){
  88.                 H[i] = y;
  89.                 if(y.b>=x.b){
  90.                         sift_up(H,i);
  91.                 }else{
  92.                         sift_down(H, n, i);
  93.                 }
  94.         }
  95. }
  96.  
  97. /*      获得堆顶元素并删除 */
  98. HEAP delete_max(HEAP H[], int &n){
  99.         HEAP x = H[1];
  100.         del(H, n, 1);
  101.         return x;
  102. }
  103.  
  104. /*      计算分支节点的上界 */
  105. void bound( KNAPNODE* node, float M, OBJECT ob[], int n){
  106.         int i = node->k;
  107.         float w = node->w;
  108.         float p = node->p;
  109.         if(node->w>M){    //        物体重量超过背包载重量
  110.                 node->b = 0;    //  上界置为0
  111.         }else{
  112.                 while((w+ob[i].w<=M)&&(i<n)){   // 否则
  113.                         w += ob[i].w;   // 计算背包已装入载重
  114.                         p += ob[i++].p; //       计算背包已装入价值
  115.                 }
  116.                 if(i<n){
  117.                         node->b = p + (M - w)*ob[i].p/ob[i].w;
  118.                 }else{
  119.                         node -> b = p;
  120.                 }
  121.         }
  122. }
  123.  
  124. /*
  125. * 用分支限界法实现0/1背包问题
  126. * 输入：包含n个物体的重量和价值的数组ob[]，背包载重量M
  127. * 输出：最优装入背包的物体obx[]，装入背包的物体最优价值v
  128. */
  129. float knapsack_bound(OBJECT ob[], float M, int n, int obx[]){
  130.         int i, k = 0;      // 堆中元素个数的计数器初始化为0
  131.         float v;
  132.         KNAPNODE *xnode, *ynode, *znode;
  133.         HEAP x, y, z, *heap;
  134.         heap = new HEAP[n*n];         // 分配堆的存储空间
  135.         for( i=0; i<n; i++){
  136.                 ob[i].v = ob[i].p/ob[i].w;      //    计算物体的价值重量比
  137.                 ob[i].num = i;        //        记录物体的初始序号
  138.         }
  139.         sort(ob,ob+n,cmp);                        //    对物体按照价值重量比排序
  140.         xnode = new KNAPNODE;         // 建立父亲结点
  141.         for( i=0; i<n; i++){            //  初始化结点
  142.                 xnode->s1[i] = false;
  143.         }
  144.         xnode->k = xnode->w = xnode->p = 0;
  145.         while(xnode->k<n) {
  146.                 ynode = new KNAPNODE;      // 建立结点y
  147.                 *ynode = *xnode;                        //      结点x的数据复制到结点y
  148.                 ynode->s1[ynode->k] = true;     //   装入第k个物体
  149.                 ynode->w += ob[ynode->k].w;     //   背包中物体重量累计
  150.                 ynode->p += ob[ynode->k].p;     //   背包中物体价值累计
  151.                 ynode->k ++;                //  搜索深度++
  152.                 bound(ynode, M, ob, n);  //       计算结点y的上界
  153.                 y.b = ynode->b;
  154.                 y.p = ynode;
  155.                 insert(heap, y, k);               //   结点y按上界的值插入堆中
  156.                 znode = new KNAPNODE;      // 建立结点z
  157.                 *znode = *xnode;                        //      结点x的数据复制到结点z
  158.                 znode->k++;                         //   搜索深度++
  159.                 bound(znode, M, ob, n);  //       计算节点z的上界
  160.                 z.b = znode->b;
  161.                 z.p = znode;
  162.                 insert(heap, z, k);               //   结点z按上界的值插入堆中
  163.                 delete xnode;
  164.                 x = delete_max(heap, k);        //      获得堆顶元素作为新的父亲结点
  165.                 xnode = x.p;
  166.         }
  167.         v = xnode->p;
  168.         for( i=0; i<n; i++){            //  取装入背包中物体在排序前的序号
  169.                 if(xnode->s1[i]){
  170.                         obx[i] = ob[i].num;
  171.                 }else{
  172.                         obx[i] = -1;
  173.                 }
  174.         }
  175.         delete xnode;
  176. /*      for(i=1; i<=k; i++) {
  177.                 delete heap[i].p;
  178.         }*/
  179.         delete heap;
  180.         return v;              //     返回背包中物体的价值
  181. }
  182.  
  183. int main(){
  184.         OBJECT ob[N];
  185.         double m;
  186.         int n, i;
  187.         int obx[N];
  188.        
  189.         cout<<"请输入背包载重：";
  190.         cin>>m;
  191.  
  192.         cout<<"请输入物品个数：";
  193.         cin>>n;
  194.  
  195.         cout<<"请输入物品重量：";
  196.         for(i=0; i<n; i++){
  197.                 cin>>ob[i].w;
  198.         }
  199.  
  200.         cout<<"请输入物品价值：";
  201.         for(i=0; i<n; i++){
  202.                 cin>>ob[i].p;
  203.         }
  204.  
  205.         double v = knapsack_bound(ob, m, n, obx);
  206.  
  207.         cout<<"装入背包的物体："<<endl;
  208.         for( i=0; obx[i]>=0&&i<n; i++){
  209.                 cout<<obx[i]<<" ";
  210.         }
  211.         cout<<endl;
  212.         cout<<"最优价值："<<v<<endl;
  213.  
  214.         return 0;
  215. }
  216.  


 

Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter