Găsiți suma maximă ponderată peste toate subsecțiunile m

Am incercat sa rezolv urmatoarea problema:

Problemă sumă ponderată

Cea mai apropiata problema pe care am facut-o inainte este algoritmul lui Kadane, asa ca am incercat abordarea "max ending here", care a condus la urmatorul program bazat pe DP. Ideea este de a sparge problema în probleme identice mai mici (DP obișnuit).

#include
#include


main(){
int i, n, m, C[20002], max, y, x, best, l, j;
int a[20002], b[20002];
scanf("%d %d", &n, &m);
for(i=0;imax) ? C[i] : max;
    a[i] = max;
}

for(l=0;lmax) ? best : max;
        }
        b[x] = max;
    }

    for(l=0;l

Dar acest program nu funcționează în limita de timp specificată (limita spațiului este fină). Vă rog să-mi dați un indiciu asupra algoritmului care va fi folosit în această problemă.

EDITAȚI | ×.

Iată explicația codului: Ca și în cazul lui Kadane, ideea mea este să privesc un anumit C [i], apoi să luăm suma maximă ponderată pentru o m-subsecvență care se termină la C [i] și, în final, să luăm maximul tuturor acestor valori peste toate i. Acest lucru ne va da răspunsul nostru. Acum, rețineți că atunci când vă uitați la o subsecțiune m terminând la C [i] și luați suma maximă ponderată, aceasta este echivalentă cu luarea sumei maxime ponderate a unei submăsuri (m-1), conținută în C [0] la C [i-1]. Și aceasta este o problemă mai mică, identică cu cea originală. Așa că recursăm. Pentru a evita dubla chemare la funcții, facem un tabel de valori f [i] [j], unde f [ii] [j] este răspunsul la problema care este identică cu problema noastră cu n înlocuită cu i și m înlocuită cu j. Asta este, vom construi o tabel de f [i] [j], iar răspunsul nostru final este f [n-1] [m] (adică vom folosi memoizarea). Acum, observând că numai o coloană anterioară este necesară pentru a calcula o intrare f [i] [j], este suficient să păstrăm doar matrice. Aceste tablouri sunt "a" și "b".

Ne pare rău pentru lungimea lungă, nu o pot ajuta. :(

0
@ VitalijZadneprovskij Vă mulțumim pentru interesul dumneavoastră. Am adaugat explicatia in postul original. Da, algoritmul meu este O (n ^ 3), motiv pentru care cred că aceasta nu este linia corectă de gândire.
adăugat autor philander_kane, sursa
Bun venit la StackOverflow! :) Mă uit la exemplul de implementare dat aici: en.wikipedia.org/wiki/Maximum_subarray_problem Se pare că algoritmul lui Kadane este liniar O (n) și codul tău este cubic O (n ^ 3). Puteți să vă comentați codul, astfel încât să puteți înțelege mai bine operațiunile pe care le faceți? De asemenea, care este semnificația variabilelor dvs., cum ar fi a și b ?
adăugat autor Vitalij Zadneprovskij, sursa

2 răspunsuri

Încercați abordarea 0/1 Knapsack without repetition în care, la fiecare pas, decideți dacă să includeți un element sau nu.

Let MWS(i, j) represent the optimal maximum weighted sum of the sub-problem C[i...N] where i varies from 0 <= i <= N and 1 <= j <= M, and our goal is to find out the value of MWS(0, 1).

MWS (i, j) pot fi reprezentate în modurile recursive după cum urmează.

enter image description here

Eu părăsesc condițiile de la limită ca un exercițiu pentru tine.

0
adăugat
Voi încerca să codific această abordare mâine. Mulțumesc foarte mult.
adăugat autor philander_kane, sursa
De fapt, acesta este exact ceea ce a sugerat Dmitri Chubarov.
adăugat autor philander_kane, sursa
atunci bine pentru tine .... acum stii atat abordarea corecta si codul de lucru :)
adăugat autor Ravi Gupta, sursa

Your general approach is correct. But there is a problem cuyour algorithm.

You could replace the body of the inner loop

    best = max = 0;
    for(j=0;jmax) ? best : max;
    }
    b[x] = max;

cu

   b[x] = MAX(b[x-1],a[x-1] + y * C[x]);

This will improve the time complexity of the algorithm. I.e. avoid recomputing b[i] for all i < x. A common trait in dynamic programming.

0
adăugat
Multumesc mult, codul a fost inutil. :) (a [x] ar fi o [x-1]. Am încercat să o editez, dar editarea este prea mică, așa că nu m-ar lăsa.)
adăugat autor philander_kane, sursa
Da, într-adevăr, ar fi o [x-1].
adăugat autor Dmitri Chubarov, sursa