(help)Find the maximum value of the sum of all arrs and the maximum value is less than target=30

463017170 — Mon, 13 Mar 2023 13:32:51 GMT

Help me！ Where is the problem？

class Solutionsubsets_targe { public: vector<double> res; void dfs(vector<double>& nums,int start,double& track,double target) { if ( track < target) { res.push_back(track); } for(int i=start;i<nums.size();i++) { if (FindDouble(res, track + nums.at(i) , 1.0E-7) < 0 ) { track += nums.at(i); } dfs(nums,i+1,track,target); track -= nums[i]; } return ; } vector<double> subsets(vector<double>& nums,double target) { double track = 0; dfs(nums,0,track,target); return res; } }; static int FindDouble(vector<double> VD, double D, double tol /*= 1.0E-7*/) { for (int i = 0; i < VD.size(); i++) { if ( fabs(VD.at(i)-D) <tol ) { return 1; } } return -1; } static void MyGroupMyCommand () { 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); Solutionsubsets_targe bb; vector<double> b= bb.subsets(arr,30); }

Re: (help)Find the maximum value of the sum of all arrs and the maximum value is less than target=30

daniel_cadext — Tue, 14 Mar 2023 00:20:14 GMT

You might have a look at Google’s OR-Tools @ https://developers.google.com/optimization

I wrapped their traveling salesman solver for autolisp, to find the shortest polyline. Anyway, they have packing solvers, Knapsack, bin-packing etc. You can use my project as a guide to working with their libraries with ARX.

BTW, some of their solvers are multi-threaded, yeah, for that CPU burn.

TSP Discussion is here: https://www.theswamp.org/index.php?topic=58049.0

My solution is here: https://drive.google.com/file/d/1wwZQ-wIL-6lh6A-QILNyzYU5-TttKeA6/view?usp=share_link

Re: (help)Find the maximum value of the sum of all arrs and the maximum value is less than target=30

463017170 — Sun, 19 Mar 2023 02:08:20 GMT

Thank you for your help! I cannot open this webpage, can I post the code to the forum?

Re: (help)Find the maximum value of the sum of all arrs and the maximum value is less than target=30

daniel_cadext — Mon, 20 Mar 2023 02:40:07 GMT

Which one? You’d need to access OR-Tools docs to see their samples, instructions etc.

Re: (help)Find the maximum value of the sum of all arrs and the maximum value is less than target=30

tbrammer — Mon, 24 Apr 2023 13:24:32 GMT

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(); }

Re: (help)Find the maximum value of the sum of all arrs and the maximum value is less than target=30

463017170 — Mon, 24 Apr 2023 13:43:12 GMT

Thank you very much. Let me learn.

topic Re: (help)Find the maximum value of the sum of all arrs and the maximum value is less than target=30 in ObjectARX Forum

(help)Find the maximum value of the sum of all arrs and the maximum value is less than target=30

Re: (help)Find the maximum value of the sum of all arrs and the maximum value is less than target=30

Re: (help)Find the maximum value of the sum of all arrs and the maximum value is less than target=30

Re: (help)Find the maximum value of the sum of all arrs and the maximum value is less than target=30

Re: (help)Find the maximum value of the sum of all arrs and the maximum value is less than target=30

Re: (help)Find the maximum value of the sum of all arrs and the maximum value is less than target=30