goma smile Posted April 18, 2016 Report Share Posted April 18, 2016 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... Quote Link to comment Share on other sites More sharing options...
Wuu Posted April 18, 2016 Report Share Posted April 18, 2016 No kurienes dati? Datubāzē, kaut kāds arrays, JSON? Uztaisi vienu objektu kur key'i ir preces id, un otru ar preces id un cenu. Sameklē pēc id un sasummē. Quote Link to comment Share on other sites More sharing options...
jurchiks Posted April 18, 2016 Report Share Posted April 18, 2016 Bet iepriekšējā sarakstā taču jau ir konkrētas preces, kāpēc jāaizstāj? Quote Link to comment Share on other sites More sharing options...
goma smile Posted April 18, 2016 Author Report Share Posted April 18, 2016 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... Quote Link to comment Share on other sites More sharing options...
codez Posted April 18, 2016 Report Share Posted April 18, 2016 Jāaizstāj pilnīgi visas preces, vai tikai daļa? Quote Link to comment Share on other sites More sharing options...
goma smile Posted April 18, 2016 Author Report Share Posted April 18, 2016 Visas Quote Link to comment Share on other sites More sharing options...
codez Posted April 18, 2016 Report Share Posted April 18, 2016 (edited) 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 April 18, 2016 by codez Quote Link to comment Share on other sites More sharing options...
goma smile Posted April 18, 2016 Author Report Share Posted April 18, 2016 Codez debešķīgi, vienīgais jautājums kā likt izpildīties tikai 1 reizi, jo tas iespējamās preces nāks pēc Random... Quote Link to comment Share on other sites More sharing options...
codez Posted April 18, 2016 Report Share Posted April 18, 2016 (edited) 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 April 18, 2016 by codez Quote Link to comment Share on other sites More sharing options...
spainis Posted April 18, 2016 Report Share Posted April 18, 2016 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) Quote Link to comment Share on other sites More sharing options...
codez Posted April 18, 2016 Report Share Posted April 18, 2016 (edited) 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 April 18, 2016 by codez Quote Link to comment Share on other sites More sharing options...
spainis Posted April 18, 2016 Report Share Posted April 18, 2016 https://en.wikipedia.org/wiki/Subset_sum_problem Quote Link to comment Share on other sites More sharing options...
codez Posted April 18, 2016 Report Share Posted April 18, 2016 Nu tur drīzāk jāsaka, ka "very special case", jo būtībā tiek atmests viens parametrs, kas ir sāls Knapsakam. Un dp risinājuma masīvs no 2D pārvēršas par 1D. Quote Link to comment Share on other sites More sharing options...
goma smile Posted April 19, 2016 Author Report Share Posted April 19, 2016 (edited) Ir gan viena sūdīga iezīme Pārlūks iefrīzo/nosprāgst, pie šāda piemēra, jo ir jāpieņem ka cenas 90% gadijumos nebūs apaļas.. https://jsfiddle.net/v4atuwww/9/ Sliktākajā gadijumā es katru preci dalīšu... Edited April 19, 2016 by goma smile Quote Link to comment Share on other sites More sharing options...
codez Posted April 19, 2016 Report Share Posted April 19, 2016 Taisi ar veseliem skaitļiem:https://jsfiddle.net/v4atuwww/10/ ar daļskaitļiem sākas floatu maģija, kur 0.1+0.4 var nebūt tas pats kas 0.2+0.3 un tādā veidā var rasties kaudze dažādu variantu un izpildes laiks uzsprāgt eksponenciāli. Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.