wyszukiwanie zadanej wartości spośród sum wartości z tablicy

[zlotowinfo]

na tą chwilę mam kod w javascript bardzo skomplikowany obliczeniowo

co przeklada się na czas generowania wyniku do kilku minut

 

<script>
data1 = new Date();


//****************dane
docelowa=500; p=[]

//losowe dane na wszelki wypadek gdyby był problem z danymi w pliku
p[1]=100.00;	p[2]=120.93;	p[3]=121.90;	p[4]=141.83;	p[5]=144.16;	p[6]=173.32;	
p[7]=177.41;	p[8]=222.93;	p[9]=266.33;	p[10]=91.85;	p[11]=95.27;	p[12]=99.33;


<?php

   $dane=file_get_contents('dane.txt');
	
   $dane=explode("zł", $dane);
   
$dane=preg_replace("/[^0-9\t,']/", "", $dane);
$dane=str_replace(',','.',$dane);
//echo $dane[2];

for($i=0;$i<count($dane)-1;$i++) 
{
//echo strpos($dane[$i],'\t');
echo("p[".($i+1)."]=".substr($dane[$i],strpos($dane[$i],"\t")+1,222).";\r\n");
}
echo "ilosc=$i;";

?>


//****************rozwiązanie

function round(round2){return Math.round(round2*100)/100 }
tolerancja=Math.round(docelowa/100)
min=docelowa-tolerancja
max=docelowa+tolerancja
dane=[]
x=1


document.write('<b>'+docelowa+'</b> - liczba docelowa ('+min+' - '+max+')<br><br>')


/*****************/function zaokrx(zaokry)
{
   zaokry=round(Math.abs(zaokry));
        if(zaokry<10) zaokry='000'+zaokry;
   else if(zaokry<100) zaokry='00'+zaokry;
   else if(zaokry<1000) zaokry='0'+zaokry;
   return zaokry;
}



function dup(arr) {
 
temp=''
    let result = arr.filter((item, index) => arr.indexOf(item) !== index);
 
    for(let x=0; x<result.length;x++) {
        return false//temp=result[x];
    }

//  if(temp!=='')return false
  return true
 
}


//alert(dup([114.5,149,237,296.63,114.5]))

for(i=1;i<=ilosc;i++)
{
   wynik=p[i];  if(wynik>=min && wynik<=max ) dane[x++]=zaokrx(docelowa-wynik)+' # '+round(wynik)+' = (1) '+p[i]; 

   for(j=1;j<=ilosc;j++)
   {  
       if(dup([i,j])) {wynik=p[i]+p[j];  if(wynik>=min && wynik<=max ) dane[x++]=zaokrx(docelowa-wynik)+' # '+round(wynik)+' = (2) '+p[i]+ ' + '+p[j]; }
       if(ilosc>=3)
       for(k=1;k<=ilosc;k++) 
       {  
          if(dup([i,j,k]))  {wynik=p[i]+p[j]+p[k];   if(wynik>=min && wynik<=max ) dane[x++]=zaokrx(docelowa-wynik)+' # '+round(wynik)+' = (3) '+p[i]+ ' + '+p[j]+ ' + '+p[k];}
          if(ilosc>=4)
          for(l=1;l<=ilosc;l++) 
          {
             if(dup([i,j,k,l]))   {wynik=p[i]+p[j]+p[k]+p[l];  if(wynik>=min && wynik<=max ) dane[x++]=zaokrx(docelowa-wynik)+' # '+round(wynik)+' = (4) '+p[i]+ ' + '+p[j]+ ' + '+p[k]+ ' + '+p[l];}
             if(ilosc>=5)
             for(m=1;m<=ilosc;m++) 
             {
                if(dup([i,j,k,l,m]))   {wynik=p[i]+p[j]+p[k]+p[l]+p[m];  if(wynik>=min && wynik<=max ) dane[x++]=zaokrx(docelowa-wynik)+' # '+round(wynik)+' = (5) '+p[i]+ ' + '+p[j]+ ' + '+p[k]+ ' + '+p[l]+ ' + '+p[m];}
                if(ilosc>=6)
                for(n=1;n<=ilosc;n++) 
                {
                   if(dup([i,j,k,l,m,n]))   {wynik=p[i]+p[j]+p[k]+p[l]+p[m]+p[n];  if(wynik>=min && wynik<=max ) dane[x++]=zaokrx(docelowa-wynik)+' # '+round(wynik)+' = (6) '+p[i]+ ' + '+p[j]+ ' + '+p[k]+ ' + '+p[l]+ ' + '+p[m]+ ' + '+p[n];}
                 if(ilosc>=7)
                   for(o=1;o<=ilosc;o++) 
                   {
                      if(dup([i,j,k,l,m,n,o]))   {wynik=p[i]+p[j]+p[k]+p[l]+p[m]+p[n]+p[o];  if(wynik>=min && wynik<=max ) dane[x++]=zaokrx(docelowa-wynik)+' # '+round(wynik)+' = (7) '+p[i]+ ' + '+p[j]+ ' + '+p[k]+ ' + '+p[l]+ ' + '+p[m]+ ' + '+p[n]+ ' + '+p[o];}
                      if(ilosc>=8)
                      for(q=1;q<=ilosc;q++) 
                      {
                         if(dup([i,j,k,l,m,n,o,q]))   {wynik=p[i]+p[j]+p[k]+p[l]+p[m]+p[n]+p[o]+p[q];  if(wynik>=min && wynik<=max ) dane[x++]=zaokrx(docelowa-wynik)+' # '+round(wynik)+' = (8) '+p[i]+ ' + '+p[j]+ ' + '+p[k]+ ' + '+p[l]+ ' + '+p[m]+ ' + '+p[n]+ ' + '+p[o]+ ' + '+p[q];}
                      }
	           }
	        }
	     }
	  }
       }
   }
}


dane.sort();	

temp=''
i=0;

if (!dane[0]) document.write('<font color=red><b>brak wartosci</b></font><br><br>'); else

for(y=0;y<=dane.length;y++) 
{ 
  if(temp!=dane[y].substring(0,dane[y].indexOf("#")))
  { 
    if(i>9)break;
    document.write((++i)+'. '+dane[y].substring(dane[y].indexOf("#")+1,99) +'<br>')
  }
  temp=dane[y].substring(0,dane[y].indexOf("#"));
  
}


data2 = new Date();
document.write('czas wyliczenia: '+((data2-data1)/1000)+'s')
</script>

 

[DawPi]

Pytanie jakieś? Problem? Kurnia, nic nie wiadomo o co Ci chodzi.

[zlotowinfo]

chodzi, ale jak już wspomniałem czas jest zbyt długi

 

czuję że zacznę wszystko od nowa, bo nie jestem w stanie ogarnąć/zmodyfikować

 

tylko jaką metodę przyjąć

Edytowane 4 Lutego przez zlotowinfo

[zlotowinfo]

i już mi pomogliście, przez to że napisałem na forum, zacząłem się zastanawiać która funkcja jest najczęściej używana, więc zmieniłem funkcję sprawdzającą duplikaty i z 306s zszedłem na 55s
 

function Dup2(arr) {
  dupi=arr.length
     if(dupi==2) return (arr[1]==arr[2])
else if(dupi==3) return (arr[1]==arr[2] || arr[1]==arr[3]                                                                                           || arr[2]==arr[3])
else if(dupi==4) return (arr[1]==arr[2] || arr[1]==arr[3] || arr[1]==arr[4]                                                                         || arr[2]==arr[3] || arr[2]==arr[4]                                                                         || arr[3]==arr[4])
else if(dupi==5) return (arr[1]==arr[2] || arr[1]==arr[3] || arr[1]==arr[4] || arr[1]==arr[5]                                                       || arr[2]==arr[3] || arr[2]==arr[4] || arr[2]==arr[5]                                                       || arr[3]==arr[4] || arr[3]==arr[5]                                                       || arr[4]==arr[5])
else if(dupi==6) return (arr[1]==arr[2] || arr[1]==arr[3] || arr[1]==arr[4] || arr[1]==arr[5] || arr[1]==arr[6]                                     || arr[2]==arr[3] || arr[2]==arr[4] || arr[2]==arr[5] || arr[2]==arr[6]                                     || arr[3]==arr[4] || arr[3]==arr[5] || arr[3]==arr[6]                                     || arr[4]==arr[5] || arr[4]==arr[6]                                     || arr[5]==arr[6])
else if(dupi==7) return (arr[1]==arr[2] || arr[1]==arr[3] || arr[1]==arr[4] || arr[1]==arr[5] || arr[1]==arr[6] || arr[1]==arr[7]                   || arr[2]==arr[3] || arr[2]==arr[4] || arr[2]==arr[5] || arr[2]==arr[6] || arr[2]==arr[7]                   || arr[3]==arr[4] || arr[3]==arr[5] || arr[3]==arr[6] || arr[3]==arr[7]                   || arr[4]==arr[5] || arr[4]==arr[6] || arr[4]==arr[7]                   || arr[5]==arr[6] || arr[5]==arr[7]                   || arr[6]==arr[7])
else if(dupi==8) return (arr[1]==arr[2] || arr[1]==arr[3] || arr[1]==arr[4] || arr[1]==arr[5] || arr[1]==arr[6] || arr[1]==arr[7] || arr[1]==arr[8] || arr[2]==arr[3] || arr[2]==arr[4] || arr[2]==arr[5] || arr[2]==arr[6] || arr[2]==arr[7] || arr[2]==arr[8] || arr[3]==arr[4] || arr[3]==arr[5] || arr[3]==arr[6] || arr[3]==arr[7] || arr[3]==arr[8] || arr[4]==arr[5] || arr[4]==arr[6] || arr[4]==arr[7] || arr[4]==arr[8] || arr[5]==arr[6] || arr[5]==arr[7] || arr[5]==arr[8] || arr[6]==arr[7] || arr[6]==arr[8] || arr[7]==arr[8])
  return true;  
}

 

 

Edytowane 4 Lutego przez zlotowinfo

[DawPi]

9 godzin temu, zlotowinfo napisał(a):

i już mi pomogliście, przez to że napisałem na forum

Zachęcam do zakupu.

https://pl.wikipedia.org/wiki/Metoda_gumowej_kaczuszki

[Mion]

A co to ma w ogóle robić ja widzę to 6 zagnieżdżonych pętli 

[zlotowinfo]

to ma wyznaczyć przybliżoną kwotę np. 500zł z kwot do zapłaty na liście p[1]..p[12]
może to być z 1 lub do 8 różnych kwot sumarycznie dających ok. 500zł

 

https://go.oga.pl/allegropay

 

jeżeli znasz jakiś lepszy algorytm, mile widziane
mój nie jest najlepszy, bo dość długo się wykonuje

 

Edytowane 5 Lutego przez zlotowinfo

[nnd.newbie]

Jeśli chodzi ci o to żeby spośród zbioru liczb wybrać takie żeby suma była jak najwyższa, ale nie przekraczała zadanej wartości to jest to problem plecakowy: https://pl.m.wikipedia.org/wiki/Problem_plecakowy

Dość klasyczny problem w informatyce i są gotowe algorytmy.

[Mion]

9 godzin temu, zlotowinfo napisał(a):

jeżeli znasz jakiś lepszy algorytm, mile widziane

Zainteresuj się AI w postaci ChatGPT 4 z wtyczką Wolfram: https://www.wolfram.com/wolfram-plugin-chatgpt/
---
I jeśli czas wykonywania jest priorytetem językiem C / C++ .

Edytowane 6 Lutego przez Mion