Liny_@NotePad

沉迷ACG中

贪心法：部分背包问题

YOYO posted @ 2009年4月29日 08:07 in 【算法】与【数据结构】 with tags 贪心 背包问题 , 5612 阅读

因可以取物体的部分放入，故每次选择价值重量比最高的物体放入，可保证放入的价值一定最大，满足贪婪选择性质和最有子结构性质，故采用贪心算法求解：
1. 根据各个物体的价值p与重量w计算价值重量比v
2. 根据v降序排序
3. 从当前最大的v的开始，判断该物体重量是否超过背包剩余载重
4. 是则放入背包剩余载重量的物体，加上这部分的价值，跳到7
5. 否则将物体完整放入背包，加上物体的价值
6. 若还有物体未放入背包，则跳到3
7. 输出背包中物体的总价值

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4.  
  5. #define N 50    //  最多输入物体数
  6.  
  7. /***********************
  8. * 存放背包属性的结构体
  9. ***********************/
  10. typedef struct{
  11.         float p;        //      物体的价值
  12.         float w;        //      物体的重量
  13.         float v;        //      物体的价值重量比
  14. }Object;
  15.  
  16. /*******************************
  17. * 比较函数：按v的递减顺序排序
  18. *******************************/
  19. bool compare(Object a, Object b){
  20.         return a.v>b.v;
  21. }
  22.  
  23. /****************************************************************
  24. * 求解背包问题的贪婪算法
  25. *
  26. * 输入：背包载重量M， 存放n个物体属性的数组instance[]，物体个数n
  27. * 输出：n个物体被装入背包的份量x[]，背包中物体的最大总价
  28. ****************************************************************/
  29. float knapsack_greedy(float m, Object instance[], float x[], int n){
  30.         int i;
  31.         float p = 0;    //  总价值初始为0
  32.  
  33.         /*      初始化     */
  34.         for(i=0; i<n; i++){     
  35.                 instance[i].v = instance[i].p / instance[i].w;  //        计算物体价值重量比
  36.                 x[i] = 0;                                                                      //     默认放入份量为0
  37.         }
  38.  
  39.         /*      对物体进行排序：按v的递减顺序   */
  40.         sort(instance,instance+n,compare);
  41.  
  42.         /*      填物过程  */
  43.         for(i=0; i<n; i++){
  44.                 if(instance[i].w<=m){         // 若物体重量小于等于剩余载重量
  45.                         x[i] = 1;                                          //     将物体全部装入 置x[i]为1
  46.                         m -= instance[i].w;               //   从剩余载重量中去掉物体的重量
  47.                         p += instance[i].p;                    //   总价值加上物体的完整价值
  48.                 }else{              //        若物体重量大于剩余载重量
  49.                         x[i] = m / instance[i].w;              //     置x[i]为剩余载重量/物体重量：即最大能置入的百分比
  50.                         p+= x[i]*instance[i].p;   //       总价值加上物体装入部分的价值
  51.                         break;            //        此时背包已满，可以退出循环
  52.                 }
  53.         }
  54.  
  55.         return p;
  56. }
  57.  
  58. /***********************
  59. * 打印换行符
  60. ***********************/
  61. void printhr(){
  62.         cout<<"------------------------------------------------------------------------"<<endl;
  63. }
  64.  
  65. int main(){
  66.         Object instance[N];          //   n个物体的属性
  67.         float x[N];                    //   n个物体装入背包的份量(0<=x[i]<=1)
  68.         float m;                                        //      背包的最大载重量
  69.         int n;          //        物体个数
  70.         int i;
  71.  
  72.         /* 输入开始 */
  73.         cout<<"请输入背包的载重量：";
  74.         cin>>m;
  75.  
  76.         cout<<"请输入物体的个数：";
  77.         cin>>n;
  78.  
  79.         cout<<"请输入物体的价格、重量："<<endl;
  80.         printhr();
  81.         for(i=0; i<n; i++){
  82.                 cout<<"【第"<<(i+1)<<"件物品】";
  83.                 cin>>instance[i].p>>instance[i].w;
  84.                 printhr();
  85.         }
  86.         /* 输入结束 */
  87.  
  88.  
  89.         /* 计算最大价值和各物体装入的重量 */
  90.         float maxv = knapsack_greedy(m, instance, x, n);
  91.  
  92.  
  93.         /* 输出开始 */
  94.         cout<<endl<<endl<<"可装入的最大价值是："<<maxv<<endl;
  95.         printhr();
  96.  
  97.         cout<<"每个物体各装入："<<endl;
  98.         printhr();
  99.         for( i=0; i<n; i++){
  100.                 cout<<"【第"<<(i+1)<<"件物品】";
  101.                 cout<<"价值："<<instance[i].p<<" 总量："<<instance[i].w<<" 价值总量比："<<instance[i].v<<" 放入数量："<<x[i]*instance[i].w<<endl;
  102.                 printhr();
  103.         }
  104.         /* 输出结束 */
  105.  
  106.         return 0;
  107. }
Small_feed 评论 (0)

登录 *


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