• <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循環(huán)用for_each來替換?;蛘邔⒐玫膄or流程用函數替代
              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

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

            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            導航

            統(tǒng)計

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久久久九九精品影院| 思思久久好好热精品国产| 久久天天躁狠狠躁夜夜网站| 久久久这里只有精品加勒比| 色婷婷综合久久久久中文一区二区| 色偷偷88888欧美精品久久久| 亚洲一区中文字幕久久| 亚洲欧美一区二区三区久久| 久久水蜜桃亚洲av无码精品麻豆| 国产精品久久久久9999| 国内精品久久久久影院亚洲| 久久96国产精品久久久| 亚洲va中文字幕无码久久| 久久久久女教师免费一区| 久久99国内精品自在现线| 亚洲午夜精品久久久久久浪潮 | 漂亮人妻被中出中文字幕久久 | 久久久久亚洲精品无码网址| 亚洲国产精品无码久久| 久久无码人妻精品一区二区三区| 国产精品美女久久久久久2018| 中文字幕久久亚洲一区| 国产精品gz久久久| 久久最近最新中文字幕大全| 无码精品久久久久久人妻中字| 亚洲性久久久影院| 久久精品国产99久久丝袜| 国产精品成人久久久久三级午夜电影 | 2021国内精品久久久久久影院| 狠狠狠色丁香婷婷综合久久五月| 日本欧美久久久久免费播放网| 综合久久久久久中文字幕亚洲国产国产综合一区首 | 26uuu久久五月天| 久久线看观看精品香蕉国产| 国产成人久久激情91| 精品久久久久久国产91| 99久久精品国产麻豆| 婷婷综合久久中文字幕| 精品久久国产一区二区三区香蕉| 精品久久久久一区二区三区| 久久久人妻精品无码一区|