εύρεση βέλτιστου αθροίσματος υποσυνόλου από σειρές θετικών ακεραίων

[kaliakman]

Μερικές ερωτήσεις:

1. Αυτό το πρόβλημα σου δόθηκε έτσι ή εσύ έχεις μεταφράσει το πρόβλημα που αντιμετωπίζεις σε αυτό που μας περιγράφεις;
2. Τα στοιχεία μπορούν να μπουν πολλές φορές στο άθροισμα (μαντεύω πως ναι μιας και λες μπορείς να έχεις πολλά μηδενικά)
3. Δεν σε ενδιαφέρει η θέση των στοιχείων στην κάθε λίστα αλλά το μόνο που σε νοιάζει είναι να έχεις τα λιγότερα δυνατά στοιχεία(count of non-zeros) όπου και αν βρίσκονται;

Αν η απάντηση στις ερωτήσεις 2+3 είναι ναι η λύση είναι αρκετά απλή.

 

14 ώρες πριν, virxen75 είπε

χονδρικά ψάχνεις κάτι τέτοιο 

 

var wh = [0, 8, 16, 25, 35, 46, 58, 71, 86, 102, 120, 140, 163, 188, 216, 
    247, 282, 321, 364, 412, 466, 526, 592, 666, 749, 841, 944, 1058, 1185,
     1326, 1484, 1659, 1854, 2072, 2314, 2583, 2883, 3216, 3588, 4001, 4461,
      4973, 5543, 6177, 6883, 7669, 8544, 9518, 10602, 11808, 13152, 14647, 
      16312, 18166, 20230, 22528, 25088, 27937, 31111, 34646, 38583, 42968, 
      47853, 53295, 59357, 66111, 73637, 82022, 91366, 101780, 113386, 126322,
       140741, 156814, 174734, 194712, 216988, 241827, 269526, 300418, 334872,
        373303, 416173, 463997, 517354, 576887];
var dp = [0, 32, 65, 101, 139, 181, 227, 277, 331, 392, 458, 531, 611, 700, 
    797, 905, 1024, 1154, 1298, 1457, 1632, 1824, 2037, 2271, 2528, 2812, 3125,
     3470, 3849, 4267, 4727, 5234, 5792, 6406, 7083, 7827, 8647, 9549, 10542, 11635,
      12838, 14161, 15619, 17222, 18987, 20930, 23068, 25421, 28010, 30860, 33996, 
      37448, 41248, 45429, 50032, 55098, 60673, 66811, 73567, 81003, 89190, 98202,
       108123, 119046, 131072, 144312, 158890, 174943, 192619, 212084, 233519, 257127,
        283127, 311763, 343305, 378049, 416322, 458484, 504934, 556109, 612494];

var X=79;
var new_wh = wh.filter(function(x) {return x <=X;});
var new_dp = dp.filter(function(x) {return x <=X;});
console.log(new_wh);
console.log(new_dp);

var arrayLength1 = new_wh.length;
var arrayLength2 = new_dp.length;
// number = j1+j2+j3+j4+j5  +  i1+i2+i3

var array=[0,0,0,0,0,0,0,0]
var number=0
exit:
for (var i3 = 0; i3 <arrayLength2; i3++) {
    for (var i2 = 0; i2 <arrayLength2; i2++) {
        for (var i1 = 0; i1 <arrayLength2; i1++) {
            for (var j5 = 0; j5 <arrayLength1; j5++) {
                for (var j4 = 0; j4 <arrayLength1; j4++) {
                    for (var j3 = 0; j3 <arrayLength1; j3++) {
                        for (var j2 = 0; j2 <arrayLength1; j2++) {
                            for (var j1 = 0; j1 <arrayLength1; j1++) {
                                number=new_wh[j1]+new_wh[j2]+new_wh[j3]+new_wh[j4]+new_wh[j5]+new_dp[i1]+new_dp[i2]+new_dp[i3]
                                if (number>=X) {
                                    array=[j1,j2,j3,j4,j5,i1,i2,i3]
                                    console.log(new_wh[j1],new_wh[j2],new_wh[j3],new_wh[j4],new_wh[j5],new_dp[i1],new_dp[i2],new_dp[i3],"=",number)
                                    console.log("positions:",array)
                                    break exit
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

 

Έχεις πολυπλοκότητα O^(n^8) το οποίο δεν θα πάει και πολύ καλά άμα μεγαλώσει η λίστα. Επίσης το `break exit` σε ξαναγυρίζει στην αρχή των for?

Επεξ/σία 1 Νοεμβρίου 2022 από kaliakman

[virxen75]

break exit βγαίνει έξω από όλα τα for

[panos78]

Το κατάλαβα.
Οι δοκιμές που έκανα φαίνονται εδώ.
Έχω αλλάξει τη σειρά των loops και βελτιώθηκε αρκετά η κατάσταση.
Νομίζω ότι αν σπάσει η διαδικασία στα 4 εσωτερικά loops και στη συνέχεια στα 4 εξωτερικά με ένα if else για τη συνθήκη Χ <= 2378764940 ίσως λύσει το πρόβλημα αλλά δεν είναι και σίγουρος.

@kaliakman
1. Μου δόθηκε έτσι
2. Η απάντηση είναι θετική και για τη 2 και για τη 3.

[kaliakman]

Αν μπορείς να πάρεις όλα τα νούμερα πολλές φορές είναι trivial:

1.  Βρίσκεις το max σε κάθε λίστα.
2. Βλέπεις αν ένα από τα δύο αρκεί, τότε τελείωσες.
3. Αν όχι τότε παίρνεις αυτό το μεγαλύτερο από τα 2 πολλές φορές μέχρι να ικανοποιείται η συνθήκη που θέλεις.
4. Αν ούτε αυτό φτάνει (δηλαδή πήρες για παράδειγμα 5 φορες το max(wh) και πάλι είσαι κάτω από το X) τότε "γεμίζεις" και το δεύτερο μέρος με την άλλη λίστα με τον ίδιο τρόπο.
5. Αν ούτε αυτό φτάνει δεν έχεις λύση. (Μπορείς με 2 πολλαπλασιασμούς να βρεις εξαρχής αν υπάρχει λύση)

Αν δεν μπορείς να πάρεις όλα τα στοιχεία πολλές φορές εκτός του 0 το πρόβλημα τότε μπορεί να απλοποιηθεί ώς εξής με έναν greedy αλγόριθμο: 
 

1) Ταξινομείς και τις δυο λίστες (αν σε ενδιαφέρουν τα αρχικά index γίνεται να τα κρατήσεις) σε φθίνουσα σειρά.
2) Κοιτάς τις αρχές των δύο λιστών έστω `wh[0]` , `dp[0]` και παίρνεις το μεγαλύτερο νούμερο από τα δύο. Έστω το `wh[0]`
3) Κάνεις το ίδιο πράγμα με τα `wh[1]`, `dp[0]`  και πάει λέγοντας.
4) Σε κάθε βήμα κάνεις έλεγχο μήπως έφτασες τον στόχο και σταματάς.

Υπάρχει πιθανότητα να υπάρχει κάποιο edge case που δεν μου έρχεται τώρα.

[panos78]

Ο κώδικας όπως τον έδωσε ο @virxen75 φαίνεται ότι λειτουργεί όπως περιμένω να λειτουργεί.
Από ό,τι φαίνεται πρέπει να το σπάσω στα δύο για να μπορεί να λειτουργεί χωρίς προβλήματα.

 

[virxen75]

Δες αν σου δουλεύει έτσι.

 

 
  var wh = [0,8000,16401,25455,35331,46181,58159,71421,86138,102493,120687,140942,163502,
    188637,216646,247860,282647,321416,364622,412768,466416,526189,592779,666959,749584,
    841609,944094,1058219,1185297,1326787,1484315,1659690,1854922,2072252,2314171,2583453,
    2883186,3216807,3588142,4001450,4461476,4973499,5543400,6177729,6883779,7669673,8544460,
    9518219,10602179,11808851,13152172,14647676,16312668,18166439,20230485,22528769,25088000,
    27937955,31111829,34646637,38583648,42968887,47853679,53295269,59357506,66111616,73637056,
    82022473,91366775,101780329,113386298,126322135,140741251,156814887,174734197,194712581,
    216988297,241827374,269526873,300418536,334872863,373303675,416173213,463997848,517354466,576887609];
  var dp = [0,32000,65401,101073,139585,181437,227119,277128,331991,392268,458564,531535,611896,
    700427,797983,905498,1024000,1154614,1298578,1457248,1632119,1824830,2037185,2271165,2528951,2812939,
    3125764,3470326,3849813,4267731,4727939,5234678,5792619,6406896,7083160,7827629,8647143,9549229,10542172,
    11635086,12838003,14161964,15619122,17222851,18987875,20930401,23068269,25421121,28010583,30860463,33996977,
    37448993,41248299,45429902,50032358,55098129,60673986,66811447,73567262,81003948,89190382,98202448,108123754,
    119046431,131072000,144312338,158890744,174943109,192619216,212084166,233519956,257127222,283127160,311763649,
    343305589,378049493,416322336,458484710,504934306,556109751,612494861];
var X=2378764940;
var new_wh = wh.filter(function(x) {return x <=X;});
var new_dp = dp.filter(function(x) {return x <=X;});
console.log(new_wh);
console.log(new_dp);

var arrayLength1 = new_wh.length;
var arrayLength2 = new_dp.length;
// number = j1+j2+j3+j4+j5  +  i1+i2+i3

var array=[0,0,0,0,0,0,0,0];
var number=0;
var count=Math.floor(X/new_wh[arrayLength1-1]);
if (count>5) count=5;
var j=[0,0,0,0,0];
for (var jj=0;jj<count;jj++){
    j[jj]=arrayLength1-1;
}

exit:
for (var i3 = 0; i3 <arrayLength2; i3++) {
    for (var i2 = 0; i2 <arrayLength2; i2++) {
        for (var i1 = 0; i1 <arrayLength2; i1++) {
            for (var j5 = j[4]; j5 <arrayLength1; j5++) {
                for (var j4 = j[3]; j4 <arrayLength1; j4++) {
                    for (var j3 = j[2]; j3 <arrayLength1; j3++) {
                        for (var j2 = j[1]; j2 <arrayLength1; j2++) {
                            for (var j1 = j[0]; j1 <arrayLength1; j1++) {
                                number=new_wh[j1]+new_wh[j2]+new_wh[j3]+new_wh[j4]+new_wh[j5]+new_dp[i1]+new_dp[i2]+new_dp[i3]
                                console.log(number);
                                if (number>=X) {
                                    array=[j1,j2,j3,j4,j5,i1,i2,i3]
                                    console.log(new_wh[j1],new_wh[j2],new_wh[j3],new_wh[j4],new_wh[j5],new_dp[i1],new_dp[i2],new_dp[i3],"=",number)
                                    console.log("positions:",array)
                                    break exit
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

 

[panos78]

Τελικά, κατέληξα σε αυτό.
Φαίνεται να δίνει τα αποτελέσματα που αναμένω και διόρθωσα και το θέμα με τον χρόνο απόκρισης (δίνει αποτέλεσμα σε λιγότερο από 1 δευτερόλεπτο).

Σας ευχαριστώ όλους που βοηθήσατε και δώσατε λύση στο πρόβλημα.
Καλό σας βράδυ.: