Liny_@NotePad

沉迷ACG中

回溯法求解0/1背包问题

YOYO posted @ 2009年5月27日 01:47 in 【算法】与【数据结构】 with tags 回溯法 01背包 , 5121 阅读

给定背包的载重量M＝20，有6个物体，价值分别为11，8，15，18，12，6，重量分别为5，3，2，10，4，2。利用回溯法求解上述问题。

一、 算法思想描述

对每个结点考虑两种情况——放入和没放入，每个分支开始时计算该分支可能达到的最大上界，如果小于当前已经能达到的上界，则不继续计算该分支，否则深入计算，直到找到最优解为止。

二、 完整的程序以及说明

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4.  
  5. //      物体结构体
  6. typedef struct{
  7.         float w;
  8.         float p;
  9.         float v;
  10.         int id;
  11. }OBJECT;
  12.  
  13. bool cmp(OBJECT a, OBJECT b){
  14.         return a.v>b.v;
  15. }
  16.  
  17. float knapsack_back(OBJECT ob[], float M, int n, bool x[]){
  18.         int i,k;
  19.         float w_cur, p_total, p_cur, w_est, p_est;
  20.         bool *y = new bool[n+1];
  21.  
  22.         //      计算物体的价值重量比
  23.         for(i=0; i<=n; i++){
  24.                 ob[i].v = ob[i].p/ob[i].w;
  25.                 y[i] = false;
  26.         }
  27.  
  28.         //      按照物体的价值重量比降序排列
  29.         sort(ob, ob+n, cmp);
  30.  
  31.         //      初始化当前背包中的价值、重量
  32.         w_cur = p_cur = p_total = 0;
  33.  
  34.         //      已搜索的可能解的总价值初始化
  35.         k = 0;
  36.         while(k>=0){
  37.                 w_est = w_cur; p_est = p_cur;
  38.  
  39.                 //      沿当前分支可能取得的最大价值
  40.                 for( i=k; i<n; i++) {
  41.                         w_est += ob[i].w;
  42.                         if(w_est<M){
  43.                                 p_est += ob[i].p;
  44.                         }else{
  45.                                 p_est += ((M-w_est+ob[i].w)/ob[i].w)*ob[i].p;
  46.                                 break;
  47.                         }
  48.                 }
  49.  
  50.                 //      估计值大于上界
  51.                 if(p_est>p_total){
  52.                         for(i=k; i<n; i++){
  53.                                 if(w_cur+ob[i].w<=M){
  54.                                         //      可装入第i个物体
  55.                                         w_cur = w_cur + ob[i].w;
  56.                                         p_cur = p_cur + ob[i].p;
  57.                                         y[i] = true;
  58.                                 }else{
  59.                                         //      不能装入第i个物体
  60.                                         y[i] = false;
  61.                                         break;
  62.                                 }
  63.                         }
  64.                         if(i>=n){
  65.                                 //      n个物体已经全部装入
  66.                                 if(p_cur>p_total){
  67.                                         //      更新当前上限
  68.                                         p_total = p_cur;
  69.                                         k = n;
  70.                                         //      保存可能的解
  71.                                         for(i=0; i<n; i++){
  72.                                                 x[i] = y[i];
  73.                                         }
  74.                                 }
  75.                         }else{
  76.                                 //      继续装入物体
  77.                                 k = i+1;
  78.                         }
  79.                 }else{
  80.                         //      估计值小于上界时
  81.                         while((i>=0)&&(!y[i]))i--;      //    沿着右分支结点方向回溯直到左分支结点
  82.                         if(i<0)break;            // 到达根结点 算法结束
  83.                         else{                  // 修改当前值
  84.                                 w_cur -= ob[i].w;
  85.                                 p_cur -= ob[i].p;
  86.                                 y[i] = false;
  87.                                 k = i+1;                                //      搜索右分支子树
  88.                         }
  89.                 }
  90.         }
  91.         //delete y;
  92.         return p_total;
  93. }
  94.  
  95. int main(){
  96.         int n;
  97.         float m;
  98.  
  99.         cout<<"请输入背包载重：";
  100.         cin>>m;
  101.  
  102.         cout<<"请输入物品个数：";
  103.         cin>>n;
  104.  
  105.         OBJECT* ob = new OBJECT[n];
  106.         {
  107.                 cout<<"请输入物品的重量、价格："<<endl;
  108.                 for(int i=0; i<n; i++){
  109.                         cin>>ob[i].w>>ob[i].p;
  110.                         ob[i].id = i+1;
  111.                 }
  112.         }
  113.  
  114.         bool* x = new bool[n];
  115.  
  116.         float v = knapsack_back(ob, m, n, x);
  117.  
  118.         {
  119.                 cout<<"最优方案："<<endl;
  120.                 for(int i=0; i<n; i++){
  121.                         if(x[i])cout<<"["<<ob[i].id<<"] ";
  122.                 }
  123.                 cout<<endl;
  124.                 cout<<"物品总价值为："<<v<<endl;
  125.         }
  126.  
  127.         return 0;
  128. }
Small_feed 评论 (0)

登录 *


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