newplan

阿基米德在洗澡時發現浮力原理,高興得來不及穿㆖褲子,跑到街㆖大喊:Eureka(我找到了)。
posts - 39, comments - 26, trackbacks - 0, articles - 4
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

greedy 部分背包问题

Posted on 2008-05-13 17:17 山泉弯延 阅读(335) 评论(0)  编辑 收藏 引用


/*
 STL       map应用 
 
* Greedy   部分背包问题 
 
* newplan  开发时间:08.5.13  
*/
/*--------INCLUDES----------*/ 
#include 
<cstdlib>
#include 
<iostream>
#include 
<map>
#include 
<fstream> 
#include 
<iomanip>
/*--------INCLUDES----------*/ 

/*---------MACROS-----------*/
#define INPUTFILE  
"bag.txt"
/*---------MACROS-----------*/

/*----------STD-------------*/
using std::ifstream;
using std::cout;
using std::endl;
using std::map;
using std::greater;
using std::ios;
using std::setw;
/*----------STD-------------*/

/*-------GLOBAL VAL---------*/
ifstream  Fin;
int n;
int W;
int totalValue;
/*-------GLOBAL VAL---------*/

/*---------MAIN-------------*/
int main(int argc, char *argv[])
{  
 
    map
<int,int,greater<int> > goods;
    
    Fin.open(INPUTFILE);
 
    
int value;
    
    
int weight;
    
    Fin
>>W;
    
    Fin
>>n;
    
    
int i;
    
for(i=0;i<n;i++)
    {
       Fin
>>value;
       Fin
>>weight;
       goods[value]
=weight;
    }

    
for(map<int,int>::iterator it = goods.begin();it!=goods.end();it++)
    {
     cout
<<setiosflags(ios::left)<<"value:"<<setw(4)<<it->first
     
<<" weight:"<<setw(4)<<it->second<<endl;
    }
    
    
for(map<int,int>::iterator it = goods.begin();it!=goods.end();it++)
    {
      
if(W-it->second>=0)
      {
         W
-=it->second;
         totalValue
+=it->first*it->second;
         cout
<<"w="<<W<<" ";
      }
      
else 
      {
         totalValue
+=W*it->first;
         cout
<<"totalValue:"<<totalValue<<endl;
         break;  
      }
      
    }
    
    system(
"PAUSE");
    return EXIT_SUCCESS;
}
/*---------MAIN-------------*/
BAG.TXT
100   10
3   43
5   22
6    4
4   67
2    3
45  2
4   2
42  24
41  4
34  55


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理