吃完饭，上来看看，发现cobras竟然跟我一样，也搞了一个对比研究，真是无聊到一块了。

fender0107401

写在前面：本帖所产生的任何法律问题与本人无关。我只是写了点代码测试了一下，然后发个贴，仅此而已。

简单的说吧，cobras对比了一下“动态规划”和“贪心算法”在求解背包问题的对比。

详见：http://bbs.chinaunix.net/thread-4152274-1-1.html 的12楼。

他的结论跟我的差不多，贪心算法在绝大多数情况下能得到最优解。

我弄了2个版本的，一个是Matlab的，一个是C++的，时间仓促，都不敢保证没有逻辑错误。

Matlab的花了1个小时实现，C++的花了2个小时。

注：完全自己实现，没有任何抄袭。

简单的验证了一下，没有做太多的测试。

以前也没玩过这个东西，所以百度了一下，主要参考的这个，完全现学现卖，没有任何深入思考。

http://blog.csdn.net/mu399/article/details/7722810

这个写的还挺清楚的，不过就是貌似作者把表给弄颠倒了。。。。

这个算法就跟下雨差不多，从左到右，从上到下（不用从下到上，那个写博客的人是从下到上弄的，不过给出的递推公式应该是从上到下的），本质就是生产一张表，所以空间复杂度是2次方的，所以规模一大就超级慢，而且Matlab版的代码会直接告诉你内存不足。。。

先贴个Matlab的实现（对错不敢保证，因为没玩过，而且也没有太多的测试，而且花费的时间也比较少）：

这个是main_01.m用来测试，就是算上面的博客里面提供的那个问题，需要去掉dp_solver.m最后面的%disp(table)的注释。

1. 
   
2. item_w = [4, 5, 6, 2, 2];
   
3. item_v = [6, 4, 5, 3, 6];
   
4. tc     = 10;
   
5. 
   
6. tv_01 = dp_solver(item_w, item_v, tc);
   
7. tv_02 = gr_solver(item_w, item_v, tc);
   
8. 
   
9. disp(tv_01);
   
10. disp(tv_02);

复制代码

这个是main_02.m可以用来对比两个算法的性能，动态规划会越算越慢，贪心算法就非常节省资源，毕竟主要的东西就是排序，所以时间和空间复杂度就等于使用排序算法的对应值。

clc; clear; close;

test_size = 2000;

time_cost   = zeros(2, test_size);
performance = zeros(2, test_size);
pr          = zeros(1, test_size);

termination_number = 10 * test_size;

tmp_index = 1;

for index= 10:10:termination_number
    disp(tmp_index);
   
    [item_w, item_v, tc] = generate_test_model(index);
   
    tic; performance(1, tmp_index) = dp_solver(item_w, item_v, tc); time_cost(1, tmp_index) =  toc / 1;
    tic; performance(2, tmp_index) = gr_solver(item_w, item_v, tc); time_cost(2, tmp_index) =  toc / 1;
   
    tmp_index = tmp_index + 1;
end

disp(time_cost);
disp(performance);

for index = 1:1:test_size
    tmp_01 = performance(1, index);
    tmp_02 = performance(2, index);
    pr(1, index) = (tmp_01 - tmp_02) / tmp_01;
end

tmp_size = 0;

[~, tmp_size] = size(pr(pr > 0.05));

disp('The pr size is:')
disp(tmp_size);

这个是生成测试问题的函数generate_test_model.m，如果想测试其他的随机数或者是tc（我试过2和1.5乘以物品数量）的值，可以在这里面改。

1. function [item_w, item_v, tc] = generate_test_model(problem_size)
   
2.     item_v = ceil(10 * rand(1, problem_size));
   
3.     item_w = ceil(10 * rand(1, problem_size));
   
4.    
   
5.     %item_v = abs(ceil(10 * randn(1, problem_size))) + 1;
   
6.     %item_w = abs(ceil(10 * randn(1, problem_size))) + 1;
   
7.     tc     = ceil(problem_size * 1.5);
   
8. end

复制代码

这个是动态规划的计算函数：dp_solver.m

1. function tv = dp_solver(item_w, item_v, tc)
   
2.    
   
3.     [~, item_number] = size(item_w);
   
4.    
   
5.     table = zeros(item_number, tc);
   
6.    
   
7.     for index_j = 1:1:tc
   
8.         for index_i = 1:1:item_number
   
9.             tmp_w  = item_w(index_i);
   
10.             tmp_v  = item_v(index_i);
    
11.             tmp_01 = 0;
    
12.             tmp_02 = 0;
    
13.             
    
14.             if ((index_j - tmp_w) >= 0)
    
15.                 if (((index_i - 1) > 0) && ((index_j - tmp_w) > 0))
    
16.                     tmp_01 = table((index_i - 1) , (index_j - tmp_w)) + tmp_v;
    
17.                 else
    
18.                     tmp_01 = tmp_v;
    
19.                 end
    
20.             end
    
21.             
    
22.             if ((index_i - 1) > 0)
    
23.                 tmp_02 = table((index_i - 1), (index_j));
    
24.             end
    
25.             
    
26.             table(index_i, index_j) = max(tmp_01, tmp_02);
    
27.         end
    
28.     end
    
29.    
    
30.     tv = table(item_number, tc); %disp(table);
    
31. end

复制代码

这个是贪心算法的计算函数：gr_solver.m

1. function tv = gr_solver(item_w, item_v, tc)
   
2.     [~, item_number] = size(item_w);
   
3.    
   
4.     tv =  0; % tv
   
5.     w  =  0; % the initial weight
   
6.     v  =  0; % the initial value
   
7.    
   
8.     item_r_old   = zeros(1, item_number);
   
9.     result_array = zeros(1, item_number);
   
10.    
    
11.     for index = 1:1:item_number
    
12.         item_r_old(index) = item_v(index) / item_w(index);
    
13.     end
    
14.    
    
15.     [~, index_array] = sort(item_r_old, 'descend');
    
16.    
    
17.     for index = 1:1:item_number
    
18.         item_index = index_array(index);
    
19.         v = v + item_v(item_index);
    
20.         w = w + item_w(item_index);
    
21.         
    
22.         if (w > tc)
    
23.             break;
    
24.         else
    
25.             result_array(index) = item_index;
    
26.             tv = tv + item_v(item_index);
    
27.         end
    
28.     end
    
29. end

复制代码

用上述代码，计算上面的博客重的问题，可以生成下述的表。

1. tv = table(item_number, tc); %disp(table);

复制代码

默认是不输出表的，需要手工把dp_solver.m里面的上面一行里面的后面那块的注释去掉，也就是下面的样子。

1. tv = table(item_number, tc); disp(table);

复制代码

     0     0     0     6     6     6     6     6     6     6
     0     0     0     6     6     6     6     6    10    10
     0     0     0     6     6     6     6     6    10    11
     0     3     3     6     6     9     9     9    10    11
     0     6     6     9     9    12    12    15    15    15

运行main_02会发现（下面的结果是用test_size = 100算的）下面的结果，程序会输出每次的计算时间和最有的目标函数值。

最后的pr是性能的比值，具体定义是在所有计算结果中，贪心算法和动态规划的结果差距较大的实验次数，比如下面的输出就是1次，也就是说100次实验里面，只有1次差距较大。

此处，差距较大是说同样的模型两者计算结果相差超过5%。

首先输出的是计算时间对比，上面的是动态规划的，下面的是贪心算法的。从结果上看，贪心算法完胜，哈哈。

Columns 1 through 11

    0.0101    0.0002    0.0003    0.0005    0.0009    0.0011    0.0018    0.0021    0.0026    0.0032    0.0039
    0.0017    0.0001    0.0001    0.0001    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002

  Columns 12 through 22

    0.0045    0.0053    0.0062    0.0066    0.0077    0.0067    0.0077    0.0106    0.0121    0.0097    0.0093
    0.0003    0.0003    0.0003    0.0003    0.0003    0.0002    0.0002    0.0003    0.0003    0.0003    0.0003

  Columns 23 through 33

    0.0102    0.0108    0.0114    0.0123    0.0132    0.0153    0.0153    0.0163    0.0174    0.0193    0.0197
    0.0002    0.0002    0.0002    0.0002    0.0002    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003

  Columns 34 through 44

    0.0222    0.0248    0.0240    0.0255    0.0306    0.0285    0.0322    0.0333    0.0354    0.0363    0.0379
    0.0003    0.0003    0.0005    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003

  Columns 45 through 55

    0.0385    0.0448    0.0466    0.0437    0.0580    0.0597    0.0540    0.0524    0.0517    0.0537    0.0551
    0.0003    0.0009    0.0003    0.0003    0.0004    0.0003    0.0003    0.0004    0.0004    0.0004    0.0004

  Columns 56 through 66

    0.0605    0.0655    0.0666    0.0670    0.0676    0.0601    0.0652    0.0664    0.0704    0.0730    0.0756
    0.0004    0.0004    0.0004    0.0004    0.0004    0.0004    0.0004    0.0003    0.0004    0.0007    0.0004

  Columns 67 through 77

    0.0744    0.0763    0.0740    0.0745    0.0737    0.0767    0.0810    0.0813    0.0833    0.0852    0.0872
    0.0004    0.0004    0.0003    0.0004    0.0004    0.0004    0.0004    0.0004    0.0004    0.0004    0.0004

  Columns 78 through 88

    0.0915    0.0974    0.1000    0.1013    0.1038    0.1070    0.1076    0.1052    0.1109    0.1137    0.1164
    0.0004    0.0008    0.0008    0.0004    0.0004    0.0004    0.0004    0.0004    0.0004    0.0004    0.0004

  Columns 89 through 99

    0.1207    0.1259    0.1242    0.1299    0.1354    0.1320    0.1605    0.1867    0.1298    0.1351    0.1366
    0.0004    0.0004    0.0004    0.0004    0.0004    0.0004    0.0006    0.0008    0.0005    0.0004    0.0004

  Column 100

    0.1269
    0.0004

然后是计算结果对比，上面的是动态规划的，下面的是贪心算法的，基本上，多数清楚下，两者差不多。

  Columns 1 through 9

          29          58          90         134         147         222         208         266         322
          29          58          89         127         144         222         207         263         318

  Columns 10 through 18

         301         346         334         413         398         472         529         502         548
         301         344         332         413         393         470         529         496         541

  Columns 19 through 27

         643         688         637         721         783         696         812         793         834
         643         681         637         721         782         695         812         789         834

  Columns 28 through 36

         880         949         927        1008        1015        1041        1078        1021        1160
         878         945         923        1006        1011        1036        1074        1013        1160

  Columns 37 through 45

        1212        1228        1168        1293        1242        1334        1300        1270        1500
        1210        1223        1166        1286        1239        1328        1294        1264        1496

  Columns 46 through 54

        1426        1491        1528        1534        1543        1676        1645        1675        1772
        1426        1490        1523        1527        1540        1676        1639        1673        1771

  Columns 55 through 63

        1811        1789        1739        1796        1861        1952        1944        2011        1991
        1810        1789        1736        1790        1860        1949        1937        2008        1985

  Columns 64 through 72

        2101        2091        2042        2055        2198        2209        2272        2210        2255
        2100        2087        2039        2050        2193        2205        2269        2208        2253

  Columns 73 through 81

        2247        2413        2263        2317        2470        2475        2444        2558        2505
        2241        2407        2263        2312        2468        2473        2443        2555        2499

  Columns 82 through 90

        2609        2597        2581        2709        2726        2755        2788        2673        2701
        2604        2593        2580        2707        2725        2753        2784        2672        2695

  Columns 91 through 99

        2891        2892        2901        3063        2897        3197        2930        3028        3175
        2884        2885        2895        3059        2894        3192        2927        3028        3173

  Column 100

        3188
        3186

The pr size is:
     1

fender0107401

新版本的动态规划（更加节省空间资源），见 http://bbs.chinaunix.net/thread-4152816-1-1.html

下面是老版本的，跟据论坛网友的提示，我有弄了一个。

二楼来贴C++，完全是同样的计算流程。

实现的时候主要的问题是C++是从0开始计数，Matlab是从1开始计数。

如果需要求解上面的博客里面的那个问题，需要打开、关闭某些注释。

在这里混的都，基本都懂C++，我就不解释了，总之和上面的是一样的计算流程。

对比之后的结论也是一样的，不同的是用C++在我的台式机可以算规模大一点的，算到后来会变的巨慢无比，主要是动态规划的问题。。。

1. /******************************************************************************/
   
2. 
   
3. #include <stdlib.h>
   
4. #include <iostream>
   
5. #include <algorithm>
   
6. #include <vector>
   
7. 
   
8. /******************************************************************************/
   
9. 
   
10. #define random(x) (rand()%x)
    
11. 
    
12. using namespace std;
    
13. 
    
14. struct test_problem
    
15. {
    
16.     vector<int> item_w;
    
17.     vector<int> item_v;
    
18.     int         tc;
    
19.     int         tp_size;
    
20. };
    
21. 
    
22. void generate_test_model(struct test_problem *);
    
23. int  dp_solver(struct test_problem *);
    
24. int  gr_solver(struct test_problem *);
    
25. bool cmp_fun(pair<float, int>, pair<float, int>);
    
26. 
    
27. /******************************************************************************/
    
28. 
    
29. int main()
    
30. {
    
31.     srand((int)time(0));
    
32. 
    
33.     int test_size = 1000;
    
34. 
    
35.     vector<int>   performance_01(test_size, 1);
    
36.     vector<int>   performance_02(test_size, 1);
    
37.     vector<float> pr(test_size, 1);
    
38. 
    
39.     int termination_number = 10 * test_size;
    
40. 
    
41.     /*
    
42.        test_problem tp;
    
43.        int tmp_list_w[] = {4, 5, 6, 2, 2}; vector<int> item_w(tmp_list_w, tmp_list_w + 5);
    
44.        int tmp_list_v[] = {6, 4, 5, 3, 6}; vector<int> item_v(tmp_list_v, tmp_list_v + 5);
    
45. 
    
46.        tp.item_w  = item_w;
    
47.        tp.item_v  = item_v;
    
48.        tp.tc      = 10;
    
49.        tp.tp_size = 5;
    
50. 
    
51.        dp_solver(&tp);
    
52.        */
    
53. 
    
54.     int tmp_index = 0;
    
55. 
    
56.     for (int index = 10; index != termination_number + 10; index = index + 10)
    
57.     {
    
58.         test_problem tp;
    
59. 
    
60.         tp.tp_size = index;
    
61. 
    
62.         generate_test_model(&tp);
    
63. 
    
64.         performance_01[tmp_index] = dp_solver(&tp);
    
65.         performance_02[tmp_index] = gr_solver(&tp);
    
66. 
    
67.         cout << tmp_index;     
    
68.         cout << "\t\t";
    
69.         cout << performance_01[tmp_index];
    
70.         cout << "\t\t";
    
71.         cout << performance_02[tmp_index] << endl;
    
72. 
    
73.         tmp_index++;
    
74.     }
    
75. 
    
76.     return 0;
    
77. }
    
78. 
    
79. /******************************************************************************/
    
80. 
    
81. void generate_test_model(struct test_problem *tp)
    
82. {
    
83.     tp->item_w.resize(tp->tp_size);
    
84.     tp->item_v.resize(tp->tp_size);
    
85. 
    
86.     for (int index = 0; index != tp->tp_size; index++)
    
87.     {
    
88.         tp->item_w[index] = random(10) + 1;
    
89.     }
    
90. 
    
91.     for (int index = 0; index != tp->tp_size; index++)
    
92.     {
    
93.         tp->item_v[index] = random(10) + 1;
    
94.     }
    
95. 
    
96.     tp->tc = (int)(1.5 * tp->tp_size);
    
97. }
    
98. 
    
99. /******************************************************************************/
    
100. 
     
101. int dp_solver(struct test_problem *tp)
     
102. {
     
103.     vector<vector<int> > table(tp->tp_size, vector<int>(tp->tc));
     
104. 
     
105.     for (int index_j = 0; index_j != tp->tc; index_j++)
     
106.     {
     
107.         for (int index_i = 0; index_i != tp->tp_size; index_i++)
     
108.         {
     
109.             int tmp_w  = tp->item_w[index_i];
     
110.             int tmp_v  = tp->item_v[index_i];
     
111.             int tmp_01 = 0;
     
112.             int tmp_02 = 0;
     
113. 
     
114.             if ((index_j - tmp_w + 1) >= 0)
     
115.             {
     
116.                 if (((index_i - 1) >= 0) && ((index_j - tmp_w) >= 0))
     
117.                 {
     
118.                     tmp_01 = table[index_i - 1][index_j - tmp_w] + tmp_v;
     
119.                 }
     
120.                 else
     
121.                 {
     
122.                     tmp_01 = tmp_v;
     
123.                 }
     
124.             }
     
125. 
     
126.             if ((index_i - 1) >= 0)
     
127.             {
     
128.                 tmp_02 = table[index_i - 1][index_j];
     
129.             }
     
130. 
     
131.             if (tmp_01 > tmp_02)
     
132.             {
     
133.                 table[index_i][index_j] = tmp_01;
     
134.             }
     
135.             else
     
136.             {
     
137.                 table[index_i][index_j] = tmp_02;
     
138.             }
     
139.         }
     
140.     }
     
141. 
     
142.     /*
     
143.     for (int index_i = 0; index_i != tp->tp_size; index_i++)
     
144.     {
     
145.         for (int index_j = 0; index_j != tp->tc; index_j++)
     
146.         {
     
147.             cout << table[index_i][index_j];
     
148.             cout <<"\t";
     
149.         }
     
150.         cout << endl;
     
151.     }
     
152. 
     
153.     cout << endl;
     
154.     */
     
155. 
     
156.     return table[tp->tp_size - 1][tp->tc - 1];
     
157. }
     
158. 
     
159. /******************************************************************************/
     
160. 
     
161. int gr_solver(struct test_problem *tp)
     
162. {
     
163.     int tv = 0;
     
164.     int  w = 0;
     
165.     int  v = 0;
     
166. 
     
167.     vector<pair<float, int> > vec_item_r(tp->tp_size);
     
168. 
     
169.     for (int index = 0; index != tp->tp_size; index++)
     
170.     {
     
171.         float tmp_01 = (float)(tp->item_v[index]);
     
172.         float tmp_02 = (float)(tp->item_w[index]);
     
173. 
     
174.         vec_item_r[index].first  = tmp_01 / tmp_02;
     
175.         vec_item_r[index].second = index;
     
176.     }
     
177. 
     
178.     sort(vec_item_r.begin(), vec_item_r.end(), cmp_fun);
     
179. 
     
180.     for (int index = 0; index < tp->tp_size; index++)
     
181.     {
     
182.         int item_index = vec_item_r[index].second;
     
183. 
     
184.         v = v + tp->item_v[item_index];
     
185.         w = w + tp->item_w[item_index];
     
186. 
     
187.         if (w > tp->tc)
     
188.         {
     
189.             break;
     
190.         }
     
191.         else
     
192.         {
     
193.             tv = tv + tp->item_v[item_index];
     
194.         }
     
195.     }
     
196. 
     
197.     return tv;
     
198. }
     
199. 
     
200. /******************************************************************************/
     
201. 
     
202. bool cmp_fun(pair<float, int> l, pair<float, int> r)
     
203. {
     
204.     return l.first > r.first;
     
205. }
     
206. 
     
207. /******************************************************************************/

复制代码

fender0107401

尽管上述两贴的代码都能正确求解 http://blog.csdn.net/mu399/article/details/7722810 中所示例的问题，但是我没法保证整个计算流程完全正确。

我尝试了改变测试问题的生成算法（也就是测试了不同类型的测试问题），但是基本结论还是没啥变化，也就是说，直接贪心算法得了，容易实现，计算效率高，而且可以求解大规模问题，动态规划虽然能得到最优解，但是计算复杂度不咋地，规模一大，就歇菜了。

除了上述算法，我其实还尝试了一些其他的算法（真是有些无聊过分了。。。），小规模时都行，大规模时都比较差，结果效果不太理想，哈哈，这里就不贴什么了。

fender0107401

至于裸奔啥的，就算了吧。

当时的情况是这样的：

3没完没了四处说fender0107401不会写代码，于是fender0107401决定调戏一下3：http://bbs.chinaunix.net/thread-4151964-1-2.html

然后3真发了个贴，http://bbs.chinaunix.net/thread-4152000-1-1.html，然后还信誓旦旦的要去裸奔。

fender0107401觉得玩大了，然后发了个Matlab的贪心算法的代码，http://bbs.chinaunix.net/thread-4152095-1-1.html

由于fender0107401发的是Matlab写的贪心算法，所以3就不用裸奔了，然后3就胜利了。

转过天来fender0107401突然想看看动态规划和贪心算法有多大差距，所以fender0107401就搞了个对比研究。

---------------------------------------------------------------------------------------------------

体现一个人编程水平的不是求解个什么问题、贴几段代码，这些东西都是非常基础的。

只要搞清楚了计算流程，实现什么的根本不是事，更重要的是设计，而不是语法什么的。

如果非要从代码上体现，那我觉得命名规则都比求解一个背包问题更能体现一个人的水平。

一个背包问题能代表啥啊？闻道有先后，术业有专攻，如是而已。

专门研究算法又如何，每种算法都会？专门研究数据结构又如何，每种数据结构都懂？专门研究操作系统又如何，每个命令都会用？专门研究网络又如何，每个协议都懂？每个网络设备都会摆弄？

最后在重复一遍，本帖导致的任何法律问题与本人无关，我只是闲着无聊，测试了一下，然后发个贴。

fender0107401

回复 5# __BlueGuy_

算了，算了，我调戏你在先，你恶心我在前。

奇葩往往都成对出现，咱俩都不是什么好鸟。。。

   

cobras

我从来没有像现在一样的深入学习一种算法。我学的更多得是数据结构。因为说实在的。平常用数据结构真的挺多的。特别是数组和链表。

cobras

这还得感谢3及时帮我补了背包问题这一课。