• <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>

            01背包問題

              1 #include <iostream>
              2 #include <vector>
              3 #include <algorithm>
              4 #define max(a,b) ((a)>(b))?(a):(b)
              5 using namespace std;
              6 //寫出來之后,嘗試把每一個for循環用for_each來替換。或者將公用的for流程用函數替代
              7 struct PrintResult 
              8 {
              9     void operator()(int i)
             10     {
             11         cout << i << " ";
             12     }
             13 }printResult;
             14 
             15 struct PrintVecResult 
             16 {
             17     void operator()(vector<int> vec)
             18     {
             19         for_each(vec.begin(), vec.end(), printResult);
             20         cout << endl;
             21     }
             22 }printVecResult;
             23 
             24 int knapsack(vector<int> &vecWeight, vector<int> &vecValue, int capacity)
             25 {
             26     int num = vecWeight.size();
             27     vector<vector<int> > f(num, vector<int>(capacity, 0));
             28     vector<int> result(num, 0);
             29 
             30     int j = 0;
             31     int i = 0;
             32     for (i = 1; i <= num; ++i)
             33     {
             34         for (j = 1; j <= capacity; ++j)
             35         {
             36             if (j >= vecWeight[i])
             37             {
             38                 f[i][j] = max(f[i-1][j], f[i-1][j-vecWeight[i]] + vecValue[i]);
             39             }
             40             else
             41             {
             42                 f[i][j] = f[i-1][j];
             43             }
             44         }
             45     }
             46     //打印f數組表
             47     for_each(f.begin(), f.end(), printVecResult);
             48     
             49     //打印背包所能容納的最大價值
             50     cout << f[num][capacity] << endl;
             51 
             52     //打印產生最大價值的背包中物品的編號
             53     
             54     for (j = capacity, i = num; i >= 1--i)
             55     {
             56         //result[i] = f[i][j] > f[i-1][j] ? 1 : 0; 
             57         if (f[i][j] > f[i-1][j])
             58         {
             59             result[i] = 1;
             60             j = j - vecWeight[i];
             61         }
             62         else
             63         {
             64             result[i] = 0;
             65         }
             66     }
             67     
             68     for (i = 1; i <= num; ++i)
             69     {
             70         if (1 == result[i])
             71         {
             72             cout << i << " ";
             73         }
             74     }
             75     return  f[num][capacity] ;
             76 }
             77 
             78 
             79 int main()
             80 {
             81     int num = 0;
             82     int capacity = 0;
             83     cin >> num;
             84     cin >> capacity;
             85 
             86     vector<int> weight;
             87     vector<int> value;
             88     weight.push_back(0);
             89     value.push_back(0);
             90 
             91     for (int i = 1; i <= num; ++i)
             92     {
             93         int tempWeight = 0;
             94         int tempValue = 0;
             95         cin >> tempWeight >> tempValue;
             96         weight.push_back(tempWeight);
             97         value.push_back(tempValue);
             98     }
             99 
            100     knapsack(weight, value, capacity);
            101 
            102     return 0;
            103 }

            posted on 2011-06-07 00:55 MrRightLeft 閱讀(329) 評論(1)  編輯 收藏 引用 所屬分類: C/C++

            評論

            # re: 01背包問題 2012-07-10 10:28 SunRise_at

            其實有個背包九講,講各種背包問題。。  回復  更多評論   

            <2011年6月>
            2930311234
            567891011
            12131415161718
            19202122232425
            262728293012
            3456789

            導航

            統計

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久久无码精品亚洲日韩软件| 国产美女久久久| 久久成人18免费网站| 久久夜色精品国产www| 伊人色综合九久久天天蜜桃| 亚洲国产精品无码久久一区二区| 久久精品人人做人人爽97| 亚洲国产精品久久久久婷婷软件| 日韩欧美亚洲国产精品字幕久久久| 东京热TOKYO综合久久精品| 日韩久久无码免费毛片软件| 亚洲精品乱码久久久久久按摩| 青青草国产精品久久久久| 午夜精品久久久久久久久| 精品熟女少妇aⅴ免费久久| 久久综合给合久久狠狠狠97色69 | 久久久国产亚洲精品| 精品国产一区二区三区久久久狼 | 久久精品国产69国产精品亚洲| 久久九九久精品国产免费直播| 久久人人爽人人爽人人片av高请 | 日韩欧美亚洲国产精品字幕久久久 | 国产成人久久精品激情 | 韩国无遮挡三级久久| 精品国产99久久久久久麻豆| 久久久久亚洲AV成人网人人网站 | 久久久久久久久无码精品亚洲日韩| 久久久久久亚洲精品不卡| av无码久久久久久不卡网站| 久久亚洲国产精品成人AV秋霞| 性欧美大战久久久久久久| 91精品国产91热久久久久福利| 国产美女久久精品香蕉69| 中文字幕日本人妻久久久免费| 中文字幕无码免费久久| 久久久久99这里有精品10| 中文字幕亚洲综合久久菠萝蜜| 亚洲国产成人精品无码久久久久久综合 | 亚洲av成人无码久久精品| 五月丁香综合激情六月久久| 精品综合久久久久久97|