Posted on 2008-05-13 17:17
山泉彎延 閱讀(432)
評論(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