现在的位置: 首页 > 综合 > 正文

用贪心法求解背包问题

2013年10月09日 ⁄ 综合 ⁄ 共 7546字 ⁄ 字号 小 中 大 ⁄ 评论关闭
贪心方法：总是对当前的问题作最好的选择，也就是局部寻优。最后得到整体最优。

应用：1：该问题可以通过“局部寻优”逐步过渡到“整体最优”，这是贪心选择性质与“动态规划”的主要差别。

2：最优子结构性质：某个问题的整体最优解包含了“子”问题的最优解。

完整的代码如下：

[cpp] view plaincopyprint?
  1. #include "iostream"
      
  2. using namespace std;  
  3.   
  4. struct goodinfo  
  5. {  
  6.     float p; //物品效益
      
  7.     float w; //物品重量
      
  8.     float X; //物品该放的数量
      
  9.     int flag; //物品编号
      
  10. };//物品信息结构体
      
  11.   
  12.   
  13. void Insertionsort(goodinfo goods[],int n)  
  14. {  
  15.     int j,i;  
  16.     for(j=2;j<=n;j++)  
  17.     {  
  18.         goods[0]=goods[j];  
  19.         i=j-1;  
  20.         while (goods[0].p>goods[i].p)  
  21.         {  
  22.             goods[i+1]=goods[i];  
  23.             i--;  
  24.         }  
  25.         goods[i+1]=goods[0];  
  26.     }  
  27.   
  28. }//按物品效益，重量比值做升序排列
      
  29.   
  30. void bag(goodinfo goods[],float M,int n)  
  31. {   
  32.   
  33.     float cu;  
  34.     int i,j;  
  35.     for(i=1;i<=n;i++)  
  36.         goods[i].X=0;  
  37.     cu=M;  //背包剩余容量
      
  38.     for(i=1;i<n;i++)  
  39.     {  
  40.         if(goods[i].w>cu)//当该物品重量大与剩余容量跳出
      
  41.             break;  
  42.         goods[i].X=1;  
  43.         cu=cu-goods[i].w;//确定背包新的剩余容量
      
  44.     }  
  45.     if(i<=n)  
  46.         goods[i].X=cu/goods[i].w;//该物品所要放的量
      
  47.   
  48.     //按物品编号做降序排列
      
  49.     for(j=2;j<=n;j++)  
  50.     {  
  51.         goods[0]=goods[j];  
  52.         i=j-1;  
  53.         while (goods[0].flag<goods[i].flag)  
  54.         {  
  55.             goods[i+1]=goods[i];  
  56.             i--;  
  57.         }  
  58.         goods[i+1]=goods[0];  
  59.     }  
  60.   
  61.     cout<<"最优解为:"<<endl;  
  62.     for(i=1;i<=n;i++)  
  63.     {  
  64.         cout<<"第"<<i<<"件物品要放:";  
  65.         cout<<goods[i].X<<endl;  
  66.     }  
  67. }  
  68.   
  69. int main(void)  
  70. {   
  71.     cout<<"|--------运用贪心法解背包问题---------|"<<endl;  
  72.     cout<<"|-------------------------------------|"<<endl;  
  73.     int i,j,n;  
  74.     float M;  
  75.     goodinfo *goods;     //定义一个指针
      
  76.     cout<<"press <1> to run the program"<<endl;  
  77.     cout<<"press <0> to exit"<<endl;  
  78.     cin>>j;  
  79.     while(j)  
  80.     {  
  81.         cout<<"请输入物品的总数量：";  
  82.         cin>>n;  
  83.         goods=new struct goodinfo [n+1];  
  84.         cout<<"请输入背包的最大容量：";  
  85.         cin>>M;  
  86.         cout<<endl;  
  87.         for(i=1;i<=n;i++)  
  88.         {  
  89.             goods[i].flag=i;  
  90.             cout<<"请输入第"<<i<<"件物品的重量:";  
  91.             cin>>goods[i].w;  
  92.             cout<<"请输入第"<<i<<"件物品的效益:";  
  93.             cin>>goods[i].p;  
  94.             goods[i].p=goods[i].p/goods[i].w;   //得出物品的效益，重量比
      
  95.             cout<<endl;  
  96.         }  
  97.   
  98.         Insertionsort(goods,n);  
  99.         bag(goods,M,n);  
  100.         cout<<"press <1> to run agian"<<endl;  
  101.         cout<<"press <0> to exit"<<endl;  
  102.         cin>>j;  
  103.     }  
  104.     system("pause");  
  105.     return 0;  
  106. }  

 

贪心方法：总是对当前的问题作最好的选择，也就是局部寻优。最后得到整体最优。

应用：1：该问题可以通过“局部寻优”逐步过渡到“整体最优”，这是贪心选择性质与“动态规划”的主要差别。

2：最优子结构性质：某个问题的整体最优解包含了“子”问题的最优解。

完整的代码如下：

[cpp] view plaincopyprint?
  1. #include "iostream"
      
  2. using namespace std;  
  3.   
  4. struct goodinfo  
  5. {  
  6.     float p; //物品效益
      
  7.     float w; //物品重量
      
  8.     float X; //物品该放的数量
      
  9.     int flag; //物品编号
      
  10. };//物品信息结构体
      
  11.   
  12.   
  13. void Insertionsort(goodinfo goods[],int n)  
  14. {  
  15.     int j,i;  
  16.     for(j=2;j<=n;j++)  
  17.     {  
  18.         goods[0]=goods[j];  
  19.         i=j-1;  
  20.         while (goods[0].p>goods[i].p)  
  21.         {  
  22.             goods[i+1]=goods[i];  
  23.             i--;  
  24.         }  
  25.         goods[i+1]=goods[0];  
  26.     }  
  27.   
  28. }//按物品效益，重量比值做升序排列
      
  29.   
  30. void bag(goodinfo goods[],float M,int n)  
  31. {   
  32.   
  33.     float cu;  
  34.     int i,j;  
  35.     for(i=1;i<=n;i++)  
  36.         goods[i].X=0;  
  37.     cu=M;  //背包剩余容量
      
  38.     for(i=1;i<n;i++)  
  39.     {  
  40.         if(goods[i].w>cu)//当该物品重量大与剩余容量跳出
      
  41.             break;  
  42.         goods[i].X=1;  
  43.         cu=cu-goods[i].w;//确定背包新的剩余容量
      
  44.     }  
  45.     if(i<=n)  
  46.         goods[i].X=cu/goods[i].w;//该物品所要放的量
      
  47.   
  48.     //按物品编号做降序排列
      
  49.     for(j=2;j<=n;j++)  
  50.     {  
  51.         goods[0]=goods[j];  
  52.         i=j-1;  
  53.         while (goods[0].flag<goods[i].flag)  
  54.         {  
  55.             goods[i+1]=goods[i];  
  56.             i--;  
  57.         }  
  58.         goods[i+1]=goods[0];  
  59.     }  
  60.   
  61.     cout<<"最优解为:"<<endl;  
  62.     for(i=1;i<=n;i++)  
  63.     {  
  64.         cout<<"第"<<i<<"件物品要放:";  
  65.         cout<<goods[i].X<<endl;  
  66.     }  
  67. }  
  68.   
  69. int main(void)  
  70. {   
  71.     cout<<"|--------运用贪心法解背包问题---------|"<<endl;  
  72.     cout<<"|-------------------------------------|"<<endl;  
  73.     int i,j,n;  
  74.     float M;  
  75.     goodinfo *goods;     //定义一个指针
      
  76.     cout<<"press <1> to run the program"<<endl;  
  77.     cout<<"press <0> to exit"<<endl;  
  78.     cin>>j;  
  79.     while(j)  
  80.     {  
  81.         cout<<"请输入物品的总数量：";  
  82.         cin>>n;  
  83.         goods=new struct goodinfo [n+1];  
  84.         cout<<"请输入背包的最大容量：";  
  85.         cin>>M;  
  86.         cout<<endl;  
  87.         for(i=1;i<=n;i++)  
  88.         {  
  89.             goods[i].flag=i;  
  90.             cout<<"请输入第"<<i<<"件物品的重量:";  
  91.             cin>>goods[i].w;  
  92.             cout<<"请输入第"<<i<<"件物品的效益:";  
  93.             cin>>goods[i].p;  
  94.             goods[i].p=goods[i].p/goods[i].w;   //得出物品的效益，重量比
      
  95.             cout<<endl;  
  96.         }  
  97.   
  98.         Insertionsort(goods,n);  
  99.         bag(goods,M,n);  
  100.         cout<<"press <1> to run agian"<<endl;  
  101.         cout<<"press <0> to exit"<<endl;  
  102.         cin>>j;  
  103.     }  
  104.     system("pause");  
  105.     return 0;  
  106. }  

 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞