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 }