(help)Find the maximum value of the sum of all arrs and the maximum value is less than target=30
Accepted solution
First: This is not an ObjectARX question at all. Maybe you get better answers if you post it to a general C++ or algorithm forum.
I'll try to help you anyway, because I like this kind of problems 😁.
Your original question was: "Where is the problem?".
Honestly I can't answer this question because I didn't understand which algorithm you tried to implement.
I wrote a console application that finds the best solution and also prints out the combination it tried to find it.
The main part of the code looks like this:
void findBest()
{
for (;;) // go forth and back until we can't go back anymore.
{
forth();
if (!back())
break;
}
}
These classes are involved:
class ValCount {
double _val; // value i.e. 10.1, 8.1,,,
unsigned _count; // how many times this value can be used. (always 1 with the sample data)
double _sumAll; // sum of (_cout * _val) of this and all follwing ValCount entries in the array
};
class Result {
vector<unsigned> _counts;
double _sum = 0.0;
};
class ValSum {
const vector<ValCount>& _valArr; // input data, preprocessed: Sorted for descending _val
const double _target; // 30.0
size_t _index; // current index
vector<unsigned> _counts; // how many times is _valArr[i]._val in the addition
double _sum; // current sum
Result _best; // current best solution
void findBest();
void forth();
void back();
}
The output looks like this:
Short explanation how forth() and back() work for the first lines:
One might expect that we need to check 2^N = 1024 combinations if we have N summands.
But actually we only need to check a small fraction of them.
The complete code is bellow. I hope the comments are sufficieent to explain how it works. Otherwise feel free to ask..
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
void fillVector(vector<double>& arr)
{
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);
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);
}
class ValCount
{
public:
ValCount(const double& v, const unsigned& cnt, const double& sumAll)
: _val(v), _count(cnt), _sumAll(sumAll)
{}
double _val;
unsigned _count;
double _sumAll;
};
static void print(const vector<unsigned>& counts, const double& sum, const double& target, const char* msg = "")
{
for (size_t i = 0; i < counts.size(); ++i)
printf("%d, ", counts[i]);
printf(" Sum = %lf, Diff = %lf%s\n", sum, target - sum, msg ? msg : "");
}
class Result
{
public:
vector<unsigned> _counts;
double _sum = 0.0;
public:
void print(const double& target, const char* msg = "")
{
::print(_counts, _sum, target, msg);
}
};
class ValSum
{
private:
const vector<ValCount>& _valArr;
const double _target;
size_t _index;
vector<unsigned> _counts;
double _sum;
Result _best;
public:
ValSum(const vector<ValCount>& valArr, double trg)
: _valArr(valArr), _sum(0.0), _counts(valArr.size(), 0), _target(trg), _index(0)
{
}
void findBest()
{
for (;;) // go forth and back until we can't go back anymore.
{
forth();
if (!back())
break;
}
}
// Here we start at index, increment index and add as many elements as possible to the addition
// All counts[i] with i>index are 0.
// We end up with index being the index of the last added element.
// If the result is better than the best result yet, we choose the new result.
void forth()
{
const size_t arrSize = _counts.size();
size_t indexNew = _index;
for (; _index < arrSize; ++_index)
{
const ValCount& vc = _valArr[_index];
unsigned n = (unsigned)((_target - _sum) / vc._val);
n = min(n, vc._count);
_counts[_index] = n;
if (n > 0)
{
_sum += vc._val * n;
indexNew = _index;
}
}
_index = indexNew; //highest modified index.
if (_sum > _best._sum)
{
// found better solution
_best._counts = _counts;
_best._sum = _sum;
_best.print(_target, " new best");
}
else
::print(_counts, _sum, _target, "");
}
// Here we start at _index and remove the last added element _counts[_index] first.
// 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
//
bool back()
{
if (_index == 0)
return false; // can't go back any further
for (;; --_index)
{
unsigned& cnt = _counts[_index];
if (cnt > 0)
{
if (_index < _counts.size() - 1)
{
--cnt;
_sum -= _valArr[_index]._val;
if (_sum + _valArr[++_index]._sumAll >= _best._sum) // can we reach target with a lower difference?
return true; // Yes. Let's go forth()
// No. Even if we sum up all remaining elements. Go back further.
}
else
{
// this is the last entry in counts[]. We can't go forth from here
_sum -= _valArr[_index]._val * cnt;
cnt = 0;
}
}
if (_index == 0)
return false; // can't go back any further (note: index is unsigned)
}
}
};
static void MyMaxSum()
{
vector<double> arr;
fillVector(arr);
map<double, unsigned> val2count;
for (const double& val : arr)
val2count[val]++;
vector<ValCount> valArr;
arr.reserve(val2count.size());
double sumAll = 0.0;
for (const auto& entry : val2count)
{
sumAll += entry.first * entry.second;
valArr.push_back(ValCount(entry.first, entry.second, sumAll));
}
reverse(valArr.begin(), valArr.end());
ValSum valsum(valArr, 30.0);
valsum.findBest();
}
int main()
{
MyMaxSum();
getchar();
}
