• <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 閱讀(328) 評論(1)  編輯 收藏 引用 所屬分類: C/C++

            評論

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

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

            <2012年7月>
            24252627282930
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            導航

            統計

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久久精品久久久久影院| 中文字幕亚洲综合久久2| 亚洲精品无码久久久久久| 久久精品亚洲精品国产色婷 | 精品综合久久久久久98| 久久亚洲春色中文字幕久久久| 国产成人久久精品二区三区| 久久久久国产精品人妻| 久久亚洲精品中文字幕三区| 久久精品卫校国产小美女| 国产香蕉97碰碰久久人人| 77777亚洲午夜久久多人| 久久精品国产99久久香蕉| 久久久久青草线蕉综合超碰| 91久久精品无码一区二区毛片| 囯产精品久久久久久久久蜜桃 | 亚洲国产成人精品无码久久久久久综合| 香蕉久久影院| 国产成人无码精品久久久久免费 | 中文精品久久久久国产网址| 国色天香久久久久久久小说| 青青热久久国产久精品 | 日本欧美久久久久免费播放网| 久久天天躁狠狠躁夜夜av浪潮| 九九99精品久久久久久| 久久亚洲AV成人出白浆无码国产| 久久久久久久精品妇女99| 中文精品久久久久人妻| 亚洲国产婷婷香蕉久久久久久| 99久久婷婷国产一区二区| 成人午夜精品久久久久久久小说 | 国产精品亚洲综合久久| 亚洲欧美一级久久精品| 色综合久久天天综线观看| 伊人久久精品影院| 人妻无码精品久久亚瑟影视| 久久婷婷五月综合色奶水99啪| 久久福利资源国产精品999| 热99RE久久精品这里都是精品免费| 亚洲国产精品无码久久久久久曰| 亚洲欧美另类日本久久国产真实乱对白|