寻找最大值

admin

1. #include <vector>
   
2. #include <map>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. void fillVector(vector<double>& arr)
   
7. {
   
8.         arr.push_back(1.1); arr.push_back(2.1); arr.push_back(3.1); arr.push_back(4.1);; arr.push_back(5.1);
   
9.         arr.push_back(6.1); arr.push_back(7.1); arr.push_back(8.1); arr.push_back(9.1);; arr.push_back(10.1);
   
10. }
    
11. 
    
12. class ValCount
    
13. {
    
14. public:
    
15.         ValCount(const double& v, const unsigned& cnt, const double& sumAll)
    
16.                 : _val(v), _count(cnt), _sumAll(sumAll)
    
17.         {}
    
18.         double   _val;
    
19.         unsigned _count;
    
20.         double   _sumAll;
    
21. };
    
22. 
    
23. static void print(const vector<unsigned>& counts, const double& sum, const double& target, const char* msg = "")
    
24. {
    
25.         for (size_t i = 0; i < counts.size(); ++i)
    
26.                 printf("%d, ", counts[i]);
    
27.         printf("  Sum = %lf, Diff = %lf%s\n", sum, target - sum, msg ? msg : "");
    
28. }
    
29. 
    
30. class Result
    
31. {
    
32. public:
    
33.         vector<unsigned>        _counts;
    
34.         double                                _sum = 0.0;
    
35. public:
    
36.         void print(const double& target, const char* msg = "")
    
37.         {
    
38.                 ::print(_counts, _sum, target, msg);
    
39.         }
    
40. };
    
41. 
    
42. class ValSum
    
43. {
    
44. private:
    
45.         const vector<ValCount>& _valArr;
    
46.         const double                    _target;
    
47.         size_t                                _index;
    
48.         vector<unsigned>        _counts;
    
49.         double                                _sum;
    
50. 
    
51.         Result                                _best;
    
52. 
    
53. public:
    
54.         ValSum(const vector<ValCount>& valArr, double trg)
    
55.                 : _valArr(valArr), _sum(0.0), _counts(valArr.size(), 0), _target(trg), _index(0)
    
56.         {
    
57.         }
    
58. 
    
59.         void findBest()
    
60.         {
    
61.                 for (;;) // go forth and back until we can't go back anymore.
    
62.                 {
    
63.                         forth();
    
64.                         if (!back())
    
65.                                 break;
    
66.                 }
    
67.         }
    
68. 
    
69.         // Here we start at index, increment index and add as many elements as possible to the addition
    
70.         // All counts[i] with i>index are 0.
    
71.         // We end up with index being the index of the last added element.
    
72.         // If the result is better than the best result yet, we choose the new result.
    
73.         void forth()
    
74.         {
    
75.                 const size_t arrSize = _counts.size();
    
76.                 size_t indexNew = _index;
    
77.                 for (; _index < arrSize; ++_index)
    
78.                 {
    
79.                         const ValCount& vc = _valArr[_index];
    
80.                         unsigned n = (unsigned)((_target - _sum) / vc._val);
    
81.                         n = min(n, vc._count);
    
82.                         _counts[_index] = n;
    
83.                         if (n > 0)
    
84.                         {
    
85.                                 _sum += vc._val * n;
    
86.                                 indexNew = _index;
    
87.                         }
    
88.                 }
    
89.                 _index = indexNew; //highest modified index.
    
90.                 if (_sum > _best._sum)
    
91.                 {
    
92.                         // found better solution
    
93.                         _best._counts = _counts;
    
94.                         _best._sum = _sum;
    
95.                         _best.print(_target, " new best");
    
96.                 }
    
97.                 else
    
98.                         ::print(_counts, _sum, _target, "");
    
99.         }
    
100. 
     
101.         // Here we start at _index and remove the last added element _counts[_index] first.
     
102.         // If the sum of all elements _valArr[i]._val with i>_index is big enough to sum up to target, we go forth with ++_index
     
103.         //
     
104.         bool back()
     
105.         {
     
106.                 if (_index == 0)
     
107.                         return false; // can't go back any further
     
108. 
     
109.                 for (;; --_index)
     
110.                 {
     
111.                         unsigned& cnt = _counts[_index];
     
112.                         if (cnt > 0)
     
113.                         {
     
114.                                 if (_index < _counts.size() - 1)
     
115.                                 {
     
116.                                         --cnt;
     
117.                                         _sum -= _valArr[_index]._val;
     
118.                                         if (_sum + _valArr[++_index]._sumAll >= _best._sum) // can we reach target with a lower difference?
     
119.                                                 return true; // Yes. Let's go forth()
     
120.                                         // No. Even if we sum up all remaining elements. Go back further.
     
121.                                 }
     
122.                                 else
     
123.                                 {
     
124.                                         // this is the last entry in counts[]. We can't go forth from here
     
125.                                         _sum -= _valArr[_index]._val * cnt;
     
126.                                         cnt = 0;
     
127.                                 }
     
128.                         }
     
129.                         if (_index == 0)
     
130.                                 return false; // can't go back any further (note: index is unsigned)
     
131.                 }
     
132.         }
     
133. };
     
134. 
     
135. static void MyMaxSum()
     
136. {
     
137.         vector<double> arr;
     
138.         fillVector(arr);
     
139. 
     
140.         map<double, unsigned> val2count;
     
141.         for (const double& val : arr)
     
142.                 val2count[val]++;
     
143. 
     
144.         vector<ValCount> valArr;
     
145.         arr.reserve(val2count.size());
     
146.         double sumAll = 0.0;
     
147.         for (const auto& entry : val2count)
     
148.         {
     
149.                 sumAll += entry.first * entry.second;
     
150.                 valArr.push_back(ValCount(entry.first, entry.second, sumAll));
     
151.         }
     
152.         reverse(valArr.begin(), valArr.end());
     
153. 
     
154.         ValSum valsum(valArr, 30.0);
     
155.         valsum.findBest();
     
156. }
     
157. 
     
158. int main()
     
159. {
     
160.         MyMaxSum();
     
161.         getchar();
     
162. }

复制代码