• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            newplan

            阿基米德在洗澡時發(fā)現(xiàn)浮力原理,高興得來不及穿上褲子,跑到街上大喊:Eureka(我找到了)。
            posts - 39, comments - 26, trackbacks - 0, articles - 4
              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

            greedy 部分背包問題

            Posted on 2008-05-13 17:17 山泉彎延 閱讀(431) 評論(0)  編輯 收藏 引用


            /*
             STL       map應(yīng)用 
             
            * Greedy   部分背包問題 
             
            * newplan  開發(fā)時間: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

            久久精品一区二区影院| 亚洲国产日韩综合久久精品| 欧美久久一级内射wwwwww.| 久久人爽人人爽人人片AV | 久久热这里只有精品在线观看| 亚洲午夜久久影院| 久久99国产精品99久久| 国产精品久久久久久福利69堂| 久久国产高潮流白浆免费观看| 久久人人爽人人爽人人AV东京热| 99久久国产宗和精品1上映| 伊人精品久久久久7777| 久久综合九色欧美综合狠狠| 麻豆精品久久精品色综合| 99精品久久久久久久婷婷| 国产情侣久久久久aⅴ免费| 99久久精品免费看国产一区二区三区 | 中文字幕久久波多野结衣av| 久久国产精品久久精品国产| 色狠狠久久AV五月综合| 婷婷综合久久中文字幕蜜桃三电影| 亚洲国产精品一区二区三区久久 | 久久国产精品99久久久久久老狼 | 亚洲精品美女久久777777| 久久亚洲色一区二区三区| 久久综合给合综合久久| 91久久九九无码成人网站 | 国产亚洲欧美精品久久久| 无码八A片人妻少妇久久| 久久午夜福利无码1000合集| 亚洲国产成人久久综合碰| 亚洲国产婷婷香蕉久久久久久| 免费一级做a爰片久久毛片潮| 亚洲国产精品无码久久青草| 色老头网站久久网| 伊人久久大香线蕉综合影院首页| 久久久久人妻精品一区| 亚洲国产精品无码久久青草| 精品久久久久久久久免费影院| 伊人久久无码精品中文字幕| 久久夜色精品国产亚洲|