Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1208966
  • 博文数量: 399
  • 博客积分: 8508
  • 博客等级: 中将
  • 技术积分: 5302
  • 用 户 组: 普通用户
  • 注册时间: 2009-10-14 09:28
个人简介

能力强的人善于解决问题,有智慧的人善于绕过问题。 区别很微妙,小心谨慎做后者。

文章分类

全部博文(399)

文章存档

2018年(3)

2017年(1)

2016年(1)

2015年(69)

2013年(14)

2012年(17)

2011年(12)

2010年(189)

2009年(93)

分类: LINUX

2009-12-29 16:47:46

解01背包问题有很多种方法,就我知道的就有动态规划,回溯法,分支界限法这几种,下面就列出我的回溯法解法,以供参考

int capacity; //背包容量

int n;        //物品数

int weight[0..n];  //物品重量数组

int price[0..n];  //物品价值数组

int cur_weight;   //当前重量

int cur_price;    //当前价值

int best_price;   //当前最优值

int best_solution[0..n];  //当前最优解

int cur_solution[0..n];   //当前解

//估计 装入第i个物品后能得到的最大价值, 从而做为剪枝的依据

int upper_bound(int i)

{

     //计算上界

     int remain_capacity = capacity - cur_weight;

     int  b = remain_capacity;

     //按单位重量的价值  递减序 装入物品

     while(i<=n && w[i]<=remain_capacity)

     {

           remain_capacity-=w[i];

           b+=p[i];

           i++;

     }

     //装满背包

     if( i<=n )

        b+=p[i]/w[i]*remain_capacity;  //准确的说这是一个上界,不是上确界

     return b;

}

void dfs(int i)

{

    //结束条件

    if(i>n)

    {

         if(best_price >cur_price)       //到此为止了,有用往后找了

         {

             for(int j=1;j<=n;j++)

                best_solution[j] =x[j];

         }

         return ;

    }

    //搜索左子树,要当前结点

    if(cur_weight+weght[i]< = capacity)

    {

         cur_solution[i] = 1;

         cur_weight += weight[i];                

         cur_price  += price[i];

         dfs(i+1);

          cur_weight   -= weight[i];                

         cur_price  -= price[i];

    }

    //搜索右子树,不要当前结点,即数组中下一个结点

    if(upper_bound(u+1)>best_price)

    {

            cur_solution[i]=0;
            dfs(i+1);

    }

}



阅读(9230) | 评论(0) | 转发(0) |
0

上一篇:整数划分问题

下一篇:面试英语技巧

给主人留下些什么吧!~~