算了算了，我错了，以后不这么玩了。

fender0107401

3，千万别裸奔，这是北京，裸奔估计得进局子，到时一问你，说是我蹿跶的，我也得跟着进去。

背包问题吗，写一个吧，中午吃饭的时候弄了一个。不是求解固定背包问题的，因为我本来打算捎带着比较一下贪心算法和进化类算法的计算效果的，所以前面有几行是随机生成背包问题的。要不多生成几个，也没法比较啊。。。。

中午那会还打算用Perl、JavaScript、PHP各实现一个，显摆一下自己会的多，C/C++什么的就得下班回家去实现了，上班没环境，不方便。

下午忙点事，回来一看，3真要出去裸奔，这闹的有点大了。。。

本版是C/C++版，3虽然没说是用那种语言实现，但是我用Matlab实现，显示不算赢，所以3不算输。况且我写的可能还不怎么对，而且我也没写其他语言版本的，哈哈。

很简单的Matlab代码，对错都算了吧，3，你千万别出去裸奔，北京不是闹着玩的。

1. 
   
2. % This is toy script. Just for fun!
   
3. % For details about the Knapsack problem, check http://en.wikipedia.org/wiki/Knapsack_problem
   
4. % There is no guarantee about the correctness of this script, as I only spent about 20 minutes to write it.
   
5. 
   
6. clc; clear; close; % general things
   
7. 
   
8. % generate a 0-1 knapsack problem
   
9. 
   
10. problem_size = 40;
    
11. w_constraint = 40;
    
12. 
    
13. item_v = ceil(10 * rand(1, problem_size)); % prevent 0 and another way is to rand and plus 1
    
14. item_w = ceil(10 * rand(1, problem_size));
    
15. 
    
16. 
    
17. w =  0; % the initial weight
    
18. v =  0; % the initial value
    
19. 
    
20. % The following line are intend to check the problem validity
    
21. 
    
22. disp(sum(item_w)); % If it is less equal w_constraint, the generated probem may be invalid.
    
23. 
    
24. disp('--------------------------------------------------------------------------------');
    
25. 
    
26. item_r_old   = zeros(1, problem_size);
    
27. result_array = zeros(1, problem_size);
    
28. 
    
29. for index = 1:1:problem_size
    
30.     item_r_old(index) = item_v(index) / item_w(index);
    
31. end
    
32. 
    
33. [item_r_new, index_array] = sort(item_r_old, 'descend');
    
34. 
    
35. disp('       v       w   item index item value item weight'); % show the computation process
    
36. for index = 1:1:problem_size
    
37.     item_index = index_array(index);
    
38.     v = v + item_v(item_index);
    
39.     w = w + item_w(item_index);
    
40.    
    
41.     fprintf('\t%4g\t%4g\t\t%4g\t\t%4g\t\t%4g\n', v, w, item_index, item_v(item_index), item_w(item_index));
    
42.    
    
43.     if (w > w_constraint)
    
44.         result_array = result_array(result_array > 0);
    
45.         disp(result_array);
    
46.         break;
    
47.     else
    
48.         result_array(index) = item_index;
    
49.     end
    
50. end
    

复制代码

Susake_

沙发~~~~~~~~

hellioncu

不懂Matlab      

nizvoo

matlab一统江湖，威武！

fender0107401

__BlueGuy_ 发表于 2014-08-27 17:42
三爷写几万行代码，也没你这么矫情啊
你能写的对才怪呢 ～

算了，3，要不你还是去裸奔吧。。。

fender0107401

__BlueGuy_ 发表于 2014-08-27 17:49
你以为你写的出来么？

3，别这样，在北京裸奔是要进局子的。。。