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 阅读(295) 评论(1)  编辑 收藏 引用 所属分类: C/C++

评论

# re: 01背包问题 2012-07-10 10:28 SunRise_at

其实有个背包九讲,讲各种背包问题。。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


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

导航

统计

随笔分类

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜