回溯： 0-1背包

 1 #include <iostream>
 2 
 3 int items[] = {0, 11,3,13,4,6,  19, 9,17, 1, 21};
 4 
 5 int limit_w = 100;
 6 
 7 int max_w = 0;
 8 
 9 void f1(int i, int cw, int* items, int n, int limit_w)
10 {
11     if(i == n || cw == limit_w)
12     {
13         if(cw > max_w) max_w = cw;
14         return;    
15     }
16 
17     f1(i + 1, cw, items, n,limit_w);
18 
19     if(cw + items[i] <= limit_w)
20     {
21         f1(i + 1, cw + items[i], items, n, limit_w);
22     }
23 }
24 
25 void f2(int i, int cw, int* items, int n, int limit_w)
26 {
27     if(i == n || cw == limit_w)
28     {
29         if(cw > max_w) max_w = cw;
30         return;    
31     }
32 
33     if(cw + items[i] <= limit_w)
34     {
35         f1(i + 1, cw + items[i], items, n, limit_w);
36     }
37 
38     f1(i + 1, cw, items, n,limit_w);
39 }
40 
41 
42 int main()
43 {
44     f1(0, 0, items, 10, limit_w);
45 
46     std::cout << "f1; max_w = " << max_w << std::endl;
47 
48     max_w = 0;
49 
50     f2(0, 0, items, 10, limit_w);
51 
52     std::cout << "f2; max_w = " << max_w << std::endl;
53 }