Jump to content
php.lv forumi

Change


goma smile

Recommended Posts

Iedoājieties, saraksts ar dažādākajām precēm to skaitu un kopējo summu...

 

Un ir saraksts ar kautkādām citām precēm kur ir norādīta summa par vienu vienību...

 

Kā varētu ar php aizstāt iepriekšējo sarakstu ar tām kautkādām precēm, lai gala summa sakristu...

Link to comment
Share on other sites

Ir viens saraksts ar precēm:

 

Kur ir orders tur ir saraksts ar X daudzumu / dažādīgumu precēm, kuras ir jāaizstājs ar precēm no saraksta kurš jau ir definētas un cenas nāk no tā paša viena saraksta, ir jaaizstāj preces ar otro sarakstu precēm, preču dažādīgums/daudzums nav svarīgs svarīga ir kopsumma...

Link to comment
Share on other sites

Nu tad jau uzdevums ir savādāks - dota summa un preču saraksts un vajag sastādīt preču grozu, kurš summā veido doto summu. Iepriekšējajam sarakstam nav nekādas nozīmes.

 

Algoritms: Uztaisi rekursīvu funkciju, kurai padot par parametru savācamo summu. Tad funkcijā ej un ņem visas preces, saglabā pagaidu masīvā un sauc funkciju rekursīvi ar par attiecīgo preci samazinātu summu.

Ja funkcijā summa sasniedz 0, tas nozīmē visa nauda iztērēta un var izdrukāt izvēlēto preču sarakstu.

https://jsfiddle.net/v4atuwww/

 

Uzlabotais variants - rekursīvajai funkcijai padod līdzi to preces indekus, kuru izmanto un kad ņem nākošās preces, sāc no tā indeka, tādā veidā izvairīsies no līdzīgiem variantiem, jo preces uz priekšu tiks ņemtas tikai augošā secībā:

https://jsfiddle.net/v4atuwww/1/

 

Variants ar vairāk precēm un lielāku summu:

https://jsfiddle.net/v4atuwww/2/

Edited by codez
Link to comment
Share on other sites

Vienkāršākais drošvien būtu sadzīt tās random preces masīvā un tad palaist šo pašu algoritmu.

 

Nedaudz sarežģītāk, pārtaisīt rekursīvo funkciju ar papildus parametru preces cena, kuru apskata un tad rekursīvi saukt funkciju 2 reizes, pirmo reizi ar to pašu cenu, nākošo reizi ar random iegūto cenu. Bet šijā gadījumā nav garantija, ka tiks apskatīti visi varianti, jo tam nepieciešams vienlaicīgi zināt vairākas cenas.

https://jsfiddle.net/v4atuwww/5/

 

P.S. Ja tev ir vajadzīgs tikai viens risinājums, tad pārtrauc iet dziļāk rekursijā, tiklīdz ir atrast kaut viens risinājums. To izdara ar papildus parametrus rekursīvai funkcijai vai kaut kur ārpusē globālāku.

Edited by codez
Link to comment
Share on other sites

Nu tad jau uzdevums ir savādāks - dota summa un preču saraksts un vajag sastādīt preču grozu, kurš summā veido doto summu. Iepriekšējajam sarakstam nav nekādas nozīmes.

 

Algoritms: Uztaisi rekursīvu funkciju, kurai padot par parametru savācamo summu. Tad funkcijā ej un ņem visas preces, saglabā pagaidu masīvā un sauc funkciju rekursīvi ar par attiecīgo preci samazinātu summu.

Ja funkcijā summa sasniedz 0, tas nozīmē visa nauda iztērēta un var izdrukāt izvēlēto preču sarakstu.

https://jsfiddle.net/v4atuwww/

 

Uzlabotais variants - rekursīvajai funkcijai padod līdzi to preces indekus, kuru izmanto un kad ņem nākošās preces, sāc no tā indeka, tādā veidā izvairīsies no līdzīgiem variantiem, jo preces uz priekšu tiks ņemtas tikai augošā secībā:

https://jsfiddle.net/v4atuwww/1/

 

Variants ar vairāk precēm un lielāku summu:

https://jsfiddle.net/v4atuwww/2/

 

Tik gadījumā sarežģītība nevelk uz O(n!) pusi? (https://jsfiddle.net/bk4uued6/1/)

 

kā arī vai šīs gadījumā nav modifcēts knapsack problem(=>np complete)

Link to comment
Share on other sites

Var taisīt dp, strādās ātrāk, bet tad risinājums sarežģītāks un ilgāk kodējams, jo dp tabulā jāglabā arī atpakaļ references, lai varētu iegūt vajadzīgo sarakstu.

 

P.S. Un knapsack īsti nav, jo nav jau 2 parametru, bet tikai viens - vieglāka par knapsack.

 

 

P.P.S

Lūk dp risinājums ar sarežģītību O(N*X), kur X = kopēja preču cena / minimālā naudas iedaļa. Vai vēl * log2(X), ja gadījumā enginē objekts ir realizēts kā binārais koks, nevis hashmaps.

https://jsfiddle.net/v4atuwww/8/

 

 

Risinājums atrod tikai vienu variantu. Ja vajadzīgi vairāki, tad katrā dp tabulas elementā ir jāglabā visas tās preču cenas ar kurām tajā nonāca un tad izvade jātaisa vai nu rekursīvi vai ar BFS.

Edited by codez
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
×
×
  • Create New...